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.
• Build a register machine compiler platform for research in program-size complexity.
• Develop "good" construction techniques for generating sparse bounded-degree broadcast graphs.
• 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?
• Implement a recently discovered minor containment (or topological containment) membership algorithm for graphs of bounded combinatorial width. Is this practical?
• Investigate new types of well-partial orders on graphs and characterize lower ideals (possibly interesting ones) by forbidden substructures.
• Complete the forbidden minor characterization of graphs that are within one vertex of Property X.
• Develop general methods for tightly bounding the pathwidth (or treewidth) of families of minor-order obstruction sets.
• Formalize graph drawing (for various families of graphs) and develop an efficient smart graph drawing system (in JAVA?).
• Some database projects are available. E.g., Sloane-like database of interesting small graphs.
• Experimental testing of hueristics for graph coloring and other hard graph problems.
• Finding induced paths/cycles in special families of graphs.

Several other practical projects are available and I am happy to discuss the possibility of pursuing other topics.

Supervised Student Topics

PhD students

• 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), <TBD>
• Kuai Wei. Parallel (CPU/GPU) Memetic Algorithms , <TBD>

MSc students

• 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 by Backtracking
• Zhou (Joe) Peng. Drawing Graphs of Bounded Treewidth / Pathwidh Treewidth
• Fengjie Wu. A Framework for Memetic Algorithms
• Alfred (Nian) Zhu. 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. Ross)
• 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

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 bipartite graphs
• 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 (MySQL/PHP)
• 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 (JSP/Tomcat/XML)
• 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 C. Calude)
• John Deverall. Websites, a catalyst for student club participation?
• Matthew Steel. Fault-tolerant network design
• Alastair Abbot. 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 bee colonies.
• 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