Research in Theory
Synopsis of the research area
Theoretical Computer Science is the branch of computer science that designs algorithmic solutions to computational problems and studies their complexity in various models of computation (automata, Turing machines, etc). Problems of interest span many areas of science and engineering, and have numerous applications in the real world.
Members of the theory group in the School of Computing are active in several areas of Theoretical Computer Science, including Complexity Theory, Graph Theory and Algorithms, Parallel and Distributed Algorithms and Systems, Combinatorial Optimization, Computational Geometry and Topology, and Quantum Computation.
An Algorithm for Finding Highest-Scoring Forbidden-Pairs Paths with Variable Vertex Scores, by M. A. Goto and E. J. Schwabe. Submitted to
Information Processing Letters, 2010.
A Dynamic Programming Algorithm for DeNovo Peptide Sequencing with Variable Scoring, by M.A. Goto and E. J. Schwabe.
Proceedings of the Fourth International Symposium on Bioinformatics Research and Applications (ISBRA'08), pp. 171-182, 2008.
Some Unexpected(ly) Open Problems, Schaefer,
Midsummer Combinatorial Workshop, Prague, 2009.
The Complexity of Nonrepetitive Coloring. Marx, Schaefer; Discrete Applied Mathematics, 157, 13--18, 2009.
Removing Independently Even Crossings, Pelsmajer, Schaefer, Štefankovič,
Crossing Number of Graphs with Rotation Systems. Pelsmajer, Schaefer, Štefankovič,
Complexity of Some Geometric Problems. Schaefer,
Graph Drawing 2009.
Strong Hanani-Tutte on the Projective Plane. Pelsmajer, Schaefer, Stasi;
SIAM Journal on Discrete Mathematics, 23(3), 1317-1323, 2009.
Spiraling and Folding: The Word View. Schaefer, Štefankovič, Sedgwick, to appear in
- An up-to-date list of Iyad Kanj’s publications can be accessed through the DBLP server at: http://dblp.uni-trier.de/pers/hd/k/Kanj:Iyad_A=