Hot Research Projects
Listed below are some research topics that I currently want to study.
Unfortunately time limitations exists and many of these nice
open problems will stay on my "wish list" for some time. These topics may
be suitable projects for both serious BSc(Hons) and graduate students.
(More information regarding these project areas is available from other
links of my home page or
by contacting me directly.)
Parallel graph algorithms for both multi-core CPUs or high-performance GPUs.
Develop "good" construction techniques for generating sparse bounded-degree
Various network design problems: (1)
for directed graphs, (2) planar networks, (3) fault-tolerant, (4)
symmetric routing protocols, (5) relaxed time, ...
Find a feasible algorithm for enumerating graphs of bounded pathwidth
and treewidth. (E.g., invent canonic forms within the basic
t-parse operator/algebraic representations.)
How to generate random graphs of bounded path/treewidth.
Compare and invent practical data clustering algorithms. What
heuristics work best for different input?
Explore quantum computing algorithms for combinatorial hard optimization problems.
Experimental testing of hueristics for graph coloring and
other hard graph problems.
Distributed algorithms, possibly using membrane computing models.
Theory and practice of graph databases.
Several other practical projects are available and I am happy to discuss
the possibility of pursuing other topics.
Supervised Student Topics
Better examples of what research topics that interest me
are illustrated by these recent students of mine.
Chi-Kou Shu. Computing Exact Approximations of a Chaitin Omega Number
(co-supervisor C. Calude), 2003
Joshua J. Arulanandham. Natural Algorithms (co-supervisor C. Calude), 2005
Masoud Khosravani. Searching for Optimal Caterpillars, 2011
Yum-Bum Kim. Distributed/Molecular computing with P Modules
(co-supervisor R. Nicolescu), 2013
Kuai Wei. Runtime Analysis of the (1+1) Memetic Algorithms, 2014
Nan Huang. Quantum and Randomness (co-supervisor C. Calude), TBA
Richard Hua. Adiabatic Quantum Computing (co-supervisor C. Calude), TBA
Nguyet Thi Nhu Tran. Global Path Planning in Three-dimensional
Constrained Spaces (co-supervisor S. Linz), TBA
Liu Xiong. Vertex Cover Obstructions and a Minor Containment Algorithm
Zili Deng. Exploiting Parse Trees for Graphs of Bounded Treewidth
Fang Guo. Finding the Minimum Broadcast Time of Bounded Degree Networks
Zhou (Joe) Peng. Drawing Graphs of Bounded Treewidth / Pathwidh
Fengjie Wu. A Framework for Memetic Algorithms
Alfred (Nian) Zhou. The Broadcasting Problem for Bounded-Degree Directed Networks
Ming Li. A Distributed Graph Algorithm Platform
Terry W. Johnson. Small World Graphs (co-supervisor C. Calude)
Rongwei Lai. Computational Expansion Approach for Network Design
Lea Chii Deng. The Evolution of Coronaviruses: SARS-CoV and
HCov-NL63 (co-supervisor H.
Kai Shang. XML Based Distributed Programming Contest Control
(co-supervisor R. Nicolescu)
Yun-Bum Kim. Graph Compounding for the (Degree, Diameter) Problem
Itamar Amith. Test sets and bounded treewidth automata.
Aisha Fenton. The Bees Algorithm for the Vehicle Routing Problem
Tania Roblot. The Computation of Finite-State Complexity
(co-supervisor C. Calude)
Sonny Datt. Membrane Topological Discovery Algorithms for P Systems
Ralph Versteegen. Computing Obstruction Sets (co-supervisor M. Conder)
Andrew Probert. An Algebraic Representation of Branch
Decomposition: Algorithms and Applications
David Elliott. Computing Obstruction Sets for Almost Outerplanar Graphs
Alex Fowler. QUBO formulations for D-wave (co-supervisor C. Calude)
Arash Heidarian. Clustering and Community Mining in Socal Networks (co-supervisor Y.S. Koh)
Niu Liu, Constructing Secure Efficient Networks
Rong Wang. Adiabatic Quantum Computing with QUBO Formulations.
Project and BSc(Hon) students
Wendy Gong. Infinite games played on finite graphs
Jianquan (John) Zhang. A linear-time pathwidth algorithm (in C++)
Haobi Wang. Broadcasting heuristics and planar networks
Liu Xiong. A CGI-based research report presentation system
Wenxiang (David) Deng. Testing a fixed-parameter vertex cover algorithm
See Mu Kim. User friendly interface for maintaining BibTex databases
Huanming Gu. Depth-first tidy layout algorithm for trees
Qinghu (Alex) Zeng. Complexity aspects of network design
Lisa Chen. Latex exercise answer book development and typesetting
Xiaomin Wang. An algorithm for enumerating all maximum matchings in
Qiaosheng Shi. An instructional automata library
Yiguo (Oliver) Yango. Grid assisted graph drawing
Lester Tan. An assignment submissions and marking system (joint with R. Nicolescu)
So (Sophia) Young Park Lee. A conference submission web server
Simona Dragomir. Register machines study (joint with C. Calude)
Danhong (Jessica) Qu. A platform independent archiving tool
Tudor (Eugen) Cristea. Technical report server front-end organizer
Jacky Wing Wai Wan. An implementation of update networks algorithms
Jarrett Walsh. Automata for graph minors
Jane He. Programming contest projects
Nordira Khoussainova. Java based implementation of finite automata algorithms
Rongwei Lai. Properties of vertex cover obstructions
Aisha Fenton. Restricted broadcast graphs and dominating set algorithms
Wang Renfeng. Project on quantum randomness (joint with C. Calude)
Yingnan (Ivy) Jiang. Simplified register machine simulator (joint with
John Deverall. Websites, a catalyst for student club participation?
Matthew Steel. Fault-tolerant network design
Alastair Abbott. Graph drawing of Cayley graphs
Samuel Melese. Improved shortest paths algorithm (with Geoff Leyland)
Jeremy Clive Read. Hybrid treemap algorithms
Mikhail Gouline. Solviing NP-complete combinatorial problems using
Danver Braganza. Academic graph library developed in Python
Konstantine Schauwecker. Ipe motivated GUI interface for GraphTex
Naraj Datt. Graph contaiment algorithms
Rosie Nan Ke. Magic sequences and characterizations
Ronald P.M. Chan. Algorithms for vertex-weighted graphs
Graham Reihana. Experimentations on arithmetic progression graphs
Nadia Kasto. Compressed register machine language and Omega
(co-supervisor C. Calude)
Anatonia Modkova. First place elimination (network flow approach)
Ralph Versteegen. Tree decompositions of Hypercube graphs (co-supervisor J. Sneddon)
Andrew Probert. A parallelized algorithm for processing graphs of bounded treewidth
Jesse Kershaw. Parallel FPT algorithm for the k-Vertex Cover
problem on a GPU device
Rong Wang. Information distribution in networks
Deqi Li. Contraction Hierarchies Algorithm: implementation and experiments
Zongcheng (Lucas) Yang. New parallel broadcast algorithm
Yiran (Ryan) Tao. Using GPU to solve difficult computational problems
Laurence McFarlane. Embedding bounded treewidth graphs into the D-wave computer architecture
Charles Auger. A database of interesting graphs within a graph database
Yicheng (Daniel) Shi. Improvements to domjudge contest system
Atiqah Dinon. Hueristic algorithms for graph embeddings
Jinming He. Similarity detection in Python programming assignments
David Dai. Vertex Cover on D-Wave quantum computer (with Cris Calude)
Zongcheng Yang. Graph embedding research for D-Wave computer architecture
Amogh Shetty. Quantum computing and its applications in machine learning
Eric Cheyne, Code similarity detection as an application of applied
(If you are a former student of mine, but omitted, please let
me know and I'll be happy to add you to the list.)