| 2009
| | Conference articles |
-
Tobias Berg and Harald Hempel:
Reoptimization of Traveling Salesperson Problems: Changing
Single Edge-Weights.
In Proceedings of the 3rd International Conference on Language
and Automata Theory and Applications
(LATA'09),
Tarragona, Spain, April 2009.
-
Nadja Betzler,
Michael R. Fellows,
Jiong Guo,
Rolf Niedermeier, and
Frances A. Rosamond:
How similarity helps to efficiently compute Kemeny rankings.
In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems
(AAMAS'09),
Budapest, Hungary, May 2009.
-
Michael Dom,
Michael R. Fellows, and
Frances A. Rosamond:
Parameterized complexity of stabbing rectangles and squares in the plane.
In Proceedings of the 3rd International Workshop on Algorithms and Computation
(WALCOM'09),
Kolkata, India, February 2009.
-
Michael R. Fellows,
Jiong Guo,
Hannes Moser, and
Rolf Niedermeier:
A generalization of Nemhauser and Trotter's local optimization theorem.
In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science
(STACS'09),
Freiburg, Germany, February 2009.
-
Hannes Moser:
Problem kernelization for graph packing.
In Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'09),
Špindlerův Mlýn, Czech Republic, January 2009.
|
| Journal articles (to appear) |
-
Jens Gramm,
Tzvika Hartman,
Till Nierhoff,
Roded Sharan, and
Till Tantau:
On the complexity of SNP block partitioning under the perfect phylogeny model.
Discrete Mathematics.
Accepted for publication, April 2008
(original publication).
-
Jiong Guo:
A more effective linear kernelization for cluster editing.
Theoretical Computer Science.
Accepted for publication, October 2008
(original publication).
-
Falk Hüffner:
Algorithm engineering for optimal graph bipartization.
Journal of Graph Algorithms and Applications.
Accepted for publication, August 2008.
-
Falk Hüffner,
Nadja Betzler, and
Rolf Niedermeier:
Separator-based data reduction for signed graph balancing.
Journal of Combinatorial Optimization.
Accepted for publication, January 2009.
-
Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Fixed-parameter algorithms for cluster vertex deletion.
Theory of Computing Systems.
Accepted for publication, September 2008
(original publication).
-
Hannes Moser and
Somnath Sikdar:
The parameterized complexity of the induced matching problem.
Discrete Applied Mathematics.
Accepted for publication, August 2008 (original
publication).
-
Hannes Moser and
Dimitrios M. Thilikos:
Parameterized Complexity of Finding Regular Induced Subgraphs.
Journal of Discrete Algorithms.
Accepted for publication, September 2008
(original publication).
|
| Book chapters (to appear) |
-
Jiong Guo,
Hannes Moser, and
Rolf Niedermeier:
Iterative Compression for Exactly Solving NP-Hard Minimization Problems.
In: Algorithmics of Large and Complex Networks,
Lecture Notes in Computer Science, Springer, 2008.
-
Sabine Helwig,
Falk Hüffner,
Ivo Rössling, and
Maik Weinard:
Algorithm Design.
In: Algorithms Engineering,
Lecture Notes in Computer Science, Springer, 2008.
-
Falk Hüffner:
Parametrisierte Ansätze für schwere Graphprobleme: Algorithmen und Experimente
(Algorithms and Experiments for Parameterized Approaches to Hard Graph Problems).
In: Ausgezeichnete Informatikdissertationen 2007,
Lecture Notes in Informatics,
GI, 2008.
-
Falk Hüffner,
Rolf Niedermeier, and
Sebastian Wernicke:
Fixed-parameter algorithms for graph-modeled data clustering.
In:
Clustering Challenges in Biological Networks,
World Scientific, 2008.
|
| 2008
| | Conference articles |
-
Tobias Berg and Harald Hempel:
Inverse problems have inverse complexity.
In Proceedings of the 5th IFIP International Conference on Theoretical
Computer Science
(TCS'08),
Milano, Italy, September 2008.
Volume 273 in IFIP International Federation for Information Processing, pages 73–86, Springer
(original publication).
-
Nadja Betzler,
Michael R. Fellows,
Jiong Guo,
Rolf Niedermeier, and
Frances A. Rosamond:
Computing Kemeny rankings, parameterized by the average KT-distance.
In Proceedings of the 2nd International Workshop on Computational Social Choice
(COMSOC'08),
Liverpool, September 2008.
Informal workshop notes.
-
Nadja Betzler,
Michael R. Fellows,
Jiong Guo,
Rolf Niedermeier, and
Frances A. Rosamond:
Fixed-parameter algorithms for Kemeny scores.
In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management
(AAIM'08),
Shanghai, China. June 2008.
Volume 5034 in Lecture Notes in Computer Science, pages 60–71, Springer
(original publication).
-
Nadja Betzler,
Michael R. Fellows,
Christian Komusiewicz, and
Rolf Niedermeier:
Parameterized algorithms and hardness results for some graph motif problems.
In Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching
(CPM'08),
Pisa, Italy. June 2008.
Volume 5029 in Lecture Notes in Computer Science, pages 31–43, Springer
(original publication).
-
Nadja Betzler,
Jiong Guo, and
Rolf Niedermeier:
Parameterized computational complexity of Dodgson and Young elections.
In Proceedings of the 11th Scandinavian Workshop on Algorithm Theory
(SWAT'08),
Gothenburg, Sweden. July 2008.
Volume 5124 in Lecture Notes in Computer Science, pages 402–413, Springer
(original publication).
-
Nadja Betzler and
Johannes Uhlmann:
Parameterized complexity of candidate control in elections and related digraph problems.
In Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications
(COCOA'08),
St. John's, Newfoundland, Canada. August 2008.
Volume 5165 in Lecture Notes in Computer Science, pages 43–53, Springer
(original publication).
-
Michael Dom,
Daniel Lokshtanov,
Saket Saurabh, and
Yngve Villanger:
Capacitated domination and covering: a parameterized perspective.
In
Proceedings of the 3rd International
Workshop on Parameterized and Exact Computation (IWPEC '08),
Victoria (BC), Canada. May 2008.
Volume 5018 in Lecture Notes in Computer Science, pages 78–90, Springer
(original publication).
-
Michael Dom and
Somnath Sikdar:
The parameterized complexity of the rectangle stabbing problem
and its variants.
In
Proceedings of the 2nd International Frontiers of Algorithmics
Workshop (FAW '08),
Changsha, China. June 2008.
Volume 5059 in Lecture Notes in Computer Science, pages 67–78, Springer
(original publication).
-
Jiong Guo,
Falk Hüffner,
Christian Komusiewicz, and
Yong Zhang:
Improved algorithms for bicluster editing.
In Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation
(TAMC'08),
Xian, China. April 2008.
Volume 4978 in Lecture Notes in Computer Science, pages 445–456, Springer
(original publication).
-
Harald Hempel and
Madlen Kimmritz:
Persistent computations.
In Proceedings of the 13th International Conference on Implementation
and Application of Automata
(CIAA'08),
San Francisco, USA. July 2008.
Volume 5148 in Lecture Notes in Computer Science, pages 171–180, Springer
(original publication).
-
Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Enumerating isolated cliques in synthetic and financial networks.
In Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications
(COCOA'08),
St. John's, Newfoundland, Canada. August 2008.
Volume 5165 in Lecture Notes in Computer Science, pages 405–416, Springer
(original publication).
-
Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Fixed-parameter algorithms for cluster vertex deletion.
In Proceedings of the 8th Latin American Theoretical Informatics Symposium
(LATIN'08),
Búzios, Brazil. April 2008.
Volume 4957 in Lecture Notes in Computer Science, pages 711–722, Springer
(original publication).
Journal version available.
-
Christian Komusiewicz and
Johannes Uhlmann:
A cubic-vertex kernel for flip consensus tree.
In Proceedings of the 28th Foundations of Software Technology and Theoretical Computer Science conference
(FSTTCS'08),
Bangalore, India. December 2008.
-
Michael Krüger and
Harald Hempel:
Approximating alternative solutions.
In Proceedings of the 14th Annual International Computing and Combinatorics Conference (COCOON'08),
Dalian, China. June 2008.
Volume 5092 in Lecture Notes in Computer Science, pages 204–214, Springer
(original publication).
-
Oriana Ponta,
Falk Hüffner, and
Rolf Niedermeier:
Speeding up dynamic programming for some NP-hard graph recoloring problems.
In Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation
(TAMC'08),
Xian, China. April 2008.
Volume 4978 in Lecture Notes in Computer Science, pages 490–501, Springer
(original publication).
|
| Journal articles |
-
Michael Dom,
Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
Closest 4-leaf power is fixed-parameter tractable.
Discrete Applied Mathematics, 156(18):3345–3361, 2008
(original publication).
-
Michael Dom,
Jiong Guo,
Rolf Niedermeier, and
Sebastian Wernicke:
Red-blue covering problems and the consecutive ones property.
Journal of Discrete Algorithms, 6(3):393–407, 2008
(original publication).
-
Stefan Eckhardt,
Sven Kosub,
Moritz G. Maaß,
Hanjo Täubig, and
Sebastian Wernicke:
Combinatorial network abstraction by trees and distances.
Theoretical Computer Science, 407(1–3):1–20, 2008
(original publication).
-
Jens Gramm,
Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
Data reduction and exact algorithms for clique cover.
ACM Journal of Experimental Algorithmics, 13, Article 2.2, 15 pages, 2008
(original publication).
-
Jens Gramm,
Arfst Nickelsen, and
Till Tantau:
Fixed-parameter algorithms in phylogenetics.
The Computer Journal,
51(1):79–101, 2008
(original publication).
-
Jiong Guo,
Rolf Niedermeier, and
Daniel Raible:
Improved algorithms and complexity results for power domination in graphs.
Algorithmica,
52(2):177–202, 2008
(original publication).
-
Jiong Guo,
Falk Hüffner,
Erhan Kenar,
Rolf Niedermeier, and
Johannes Uhlmann:
Complexity and exact algorithms for vertex multicut in interval
and bounded treewidth graphs.
European Journal of Operational Research,
186(2):542–553, 2008
(original publication).
-
Jiong Guo,
Rolf Niedermeier, and
Johannes Uhlmann:
Two fixed-parameter algorithms for vertex covering by paths on trees.
Information Processing Letters,
106(2): 81–86, 2008
(original publication).
-
Falk Hüffner,
Rolf Niedermeier, and
Sebastian Wernicke:
Techniques for practical fixed-parameter algorithms.
The Computer Journal,
51(1):7–25, 2008
(original publication).
-
Falk Hüffner,
Sebastian Wernicke, and
Thomas Zichner:
Algorithm engineering for color-coding with applications to signaling pathway detection.
Algorithmica,
52(2):114–132, 2008
(original publication).
|
| Book chapters |
-
Michael Dom,
Falk Hüffner, and
Rolf Niedermeier:
Tiefensuche (Ariadne und Co.) (Depth-First Search: Ariadne & Co.).
In:
Taschenbuch der Algorithmen, chapter 7, pages 61–73,
Springer, 2008
(original publication).
Originally appeared as part of the
Algorithmus der Woche series.
-
Michael Dom:
Set cover with almost consecutive ones property.
In: Encyclopedia of Algorithms,
Springer, pages 832–834, 2008.
-
Jens Gramm,
Arfst Nickelsen, and
Till Tantau:
Fixed-Parameter Algorithms in Phylogenetics.
In:
Bioinformatics, Volume I: Data, Sequence Analysis and Evolution,
volume 452 in
Methods in Molecular Biology,
pages 507–535,
Humana Press, 2008
(original publication).
-
Jiong Guo:
Undirected feedback vertex set.
In: Encyclopedia of Algorithms,
Springer, pages 995–996, 2008.
-
Falk Hüffner:
Automated Search Tree Generation.
In: Encyclopedia of Algorithms,
Springer, pages 78–81, 2008
(original publication).
-
Falk Hüffner,
Rolf Niedermeier, and
Sebastian Wernicke:
Developing Fixed-Parameter Algorithms to Solve Combinatorially Explosive Biological Problems.
In:
Bioinformatics, Volume II: Structure, Function and Applications,
volume 453 in
Methods in Molecular Biology,
pages 395–421,
Humana Press, 2008
(original publication).
-
Rolf Niedermeier:
Data Reduction for Domination in Graphs.
In: Encyclopedia of Algorithms,
Springer, pages 220–222, 2008.
|
| Theses |
-
Michael Dom:
Recognition, Generation, and Application of Binary Matrices with the Consecutive-Ones Property.
PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2008.
- Susanne Hemmann:
Komplexität der Bestimmung Alleiniger Möglicher Gewinner bei Borda- und
Maximin-Verfahren.
Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2008.
- Mathias Weller:
Counting, Generating, and Solving Sudoku.
Studienarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2008.
|
| 2007
| | Conference articles |
-
David B. Chandler,
Jiong Guo,
Ton Kloks, and
Rolf Niedermeier:
Probe matrix problems: totally balanced matrices.
In Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management
(AAIM'07),
Portland, USA. June 2007.
Volume 4508 in Lecture Notes in Computer Science, pages 368–377, Springer
(original publication).
-
Michael Dom,
Jiong Guo, and
Rolf Niedermeier:
Approximability and parameterized complexity of consecutive ones submatrix problems.
In Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation
(TAMC'07),
Shanghai, China. May 2007.
Volume 4484 in Lecture Notes in Computer Science, pages 680–691, Springer
(original publication).
-
Michael Dom and
Rolf Niedermeier:
The search for consecutive ones submatrices: faster and more general.
In Proceedings of the 3rd Algorithms and Complexity in Durham
(ACiD '07) Workshop,
Durham, England. September 2007.
Texts in Algorithmics, volume 9, pages 43–54. College Publications.
-
Jiong Guo:
A more effective linear kernelization for cluster editing.
In Proceedings of the International Symposium on Combinatorics, Algorithms,
Probabilistic and Experimental Methodologies
(ESCAPE'07),
Hangzhou, China. April 2007.
Volume 4614 in Lecture Notes in Computer Science, pages 36–47, Springer
(original publication).
Journal version available.
-
Jiong Guo:
Problem kernels for NP-complete edge deletion problems: split and related graphs.
In Proceedings of the 18th Annual International Symposium on Algorithms and Computation
(ISAAC'07),
Sendai, Japan. December 2007.
Volume 4835 in Lecture Notes in Computer Science, pages 915–926, Springer
(original publication).
-
Jiong Guo and
Rolf Niedermeier:
Linear problem kernels for NP-hard problems on planar graphs.
In Proceedings of the 34th International Colloquium on Automata, Languages
and Programming
(ICALP'07),
Wrocław, Poland. June 2007.
Volume 4596 in Lecture Notes in Computer Science, pages 375–386, Springer
(original publication).
-
Jiong Guo and
Johannes Uhlmann:
Kernelization and complexity results for connectivity augmentation problems.
In Proceedings of the 10th Workshop on Algorithms and Data Structures
(WADS'07),
Halifax, Canada. August 2007.
Volume 4619 in Lecture Notes in Computer Science, pages 484–495, Springer
(original publication).
-
Falk Hüffner,
Nadja Betzler, and
Rolf Niedermeier:
Optimal edge deletions for signed graph balancing.
In Proceedings of the 6th Workshop on Experimental Algorithms
(WEA'07),
Rome, Italy. June 2007.
Volume 4525 in Lecture Notes in Computer Science, pages 297–310, Springer
(original publication).
Journal version available.
-
Falk Hüffner,
Sebastian Wernicke, and
Thomas Zichner:
Algorithm engineering for color-coding to facilitate signaling pathway detection.
In Proceedings of the 5th Asia-Pacific Bioinformatics Conference
(APBC'07),
Hong Kong. January 2007.
Volume 5 in Advances in Bioinformatics and Computational Biology, pages 277–286,
Imperial College Press
(original publication).
Journal version available.
-
Christian Komusiewicz,
Falk Hüffner,
Hannes Moser, and
Rolf Niedermeier:
Isolation concepts for enumerating dense subgraphs.
In Proceedings of the 13th International Computing and Combinatorics Conference
(COCOON'07),
Banff, Canada. July 2007.
Volume 4598 in Lecture Notes in Computer Science, pages 140–150, Springer
(original publication).
-
Hannes Moser,
Venkatesh Raman, and
Somnath Sikdar:
The parameterized complexity of the unique coverage problem.
In Proceedings of the 18th Annual International Symposium on Algorithms and Computation
(ISAAC'07),
Sendai, Japan. December 2007.
Volume 4835 in Lecture Notes in Computer Science, pages 621–631, Springer.
-
Hannes Moser and
Somnath Sikdar:
The parameterized complexity of the induced matching problem in planar graphs.
In Proceedings of the 2007 International Frontiers of Algorithmics Workshop
(FAW'07),
Lanzhou, China. August 2007.
Volume 4613 in Lecture Notes in Computer Science, pages 325–336, Springer
(original publication).
- Sebastian Wernicke and
Florian Rasche:
Simple and fast alignment of metabolic pathways by exploiting local diversity.
In Proceedings of the 5th Asia-Pacific Bioinformatics Conference
(APBC'07),
Hong Kong. January 2007.
Volume 5 in Advances in Bioinformatics and Computational Biology, pages 353–362,
Imperial College Press
(original publication).
Journal version available.
|
| Journal articles |
-
Jens Gramm,
Jiong Guo,
Falk Hüffner,
Rolf Niedermeier,
Hans-Peter Piepho, and
Ramona Schmid:
Algorithms for compact letter displays: comparison and evaluation.
Computational Statistics & Data Analysis,
52(2):725–736, 2007
(original publication).
-
Jens Gramm,
Till Nierhoff,
Roded Sharan, and
Till Tantau:
Haplotyping with missing data via perfect path phylogenies.
Discrete Applied Mathematics,
155(6–7): 788–805, 2007
(original publication).
-
Jiong Guo,
Falk Hüffner, and
Hannes Moser:
Feedback arc set in bipartite tournaments is NP-complete.
Information Processing Letters,
102(2–3): 62–65, 2007
(original publication).
-
Jiong Guo and
Rolf Niedermeier:
Invitation to data reduction and problem kernelization.
ACM SIGACT News,
38(1): 31–45, 2007
(original publication).
-
Jiong Guo,
Rolf Niedermeier, and
Sebastian Wernicke:
Parameterized complexity of vertex cover variants.
Theory of Computing Systems, 41(3):501–520, 2007
(original publication).
-
Falk Hüffner,
Sebastian Wernicke, and
Thomas Zichner:
FASPAD: fast signaling pathway detection.
Bioinformatics Applications Note,
23(13): 1708–1709, 2007
(original publication).
- FASPAD for Linux (i386) or Windows (i386) and
as source code
-
Rolf Niedermeier,
Jörg Vogel,
Michael Fothe, and
Mirko König:
Das Knotenüberdeckungsproblem – eine Fallstudie zur Didaktik NP-schwerer Probleme
(Vertex cover: a case study on didactics of NP-hard problems).
LOG IN,
146/147:53–59 (part 1) and 148 (part 2), 2007.
-
Sebastian Wernicke and
Florian Rasche:
Simple and fast alignment of metabolic pathways by exploiting local diversity.
Bioinformatics,
23(15):1978–1985 2007
(original publication).
|
| Book chapters |
-
Michael Dom:
Compact Routing.
In: Algorithms for Sensor and Ad Hoc Networks,
volume 4621 in Lecture Notes in Computer Science, pages 187–202,
Springer, 2007
(original publication).
-
Jiong Guo:
Algorithmenentwurfstechniken für parametrisierte Graphmodifikationsprobleme
(Algorithm Design Techniques for Parameterized Graph Modification Problems).
In: Ausgezeichnete Informatikdissertationen 2006,
volume D-7 in Lecture Notes in Informatics, pages 99–109,
GI, 2007.
|
| Theses |
|
| 2006
| | Conference articles |
-
Jochen Alber,
Britta Dorn, and
Rolf Niedermeier:
A general data reduction scheme for domination in graphs.
In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science
(SOFSEM'06),
Merin, Czech Republic. January 2006.
Volume 3831 in Lecture Notes in Computer Science, pages 137–147, Springer
(original publication).
-
Matthias Brosemann,
Jochen Alber,
Falk Hüffner, and
Rolf Niedermeier:
Matrix robustness, with an application to power system observability.
In Proceedings of the 2nd Algorithms and Complexity in Durham
(ACiD'06),
Durham, England. September 2006.
Volume 7 in Texts in Algorithmics, pages 37–48, College Publications.
-
Michael Dom,
Jiong Guo,
Falk Hüffner,
Rolf Niedermeier, and
Anke Truß:
Fixed-parameter tractability results for feedback set problems in tournaments.
In Proceedings of the 6th Conference on Algorithms and Complexity
(CIAC'06),
Rome, Italy. May 2006.
Volume 3998 in Lecture Notes in Computer Science, pages 320–331, Springer
(original publication).
-
Michael Dom,
Jiong Guo,
Rolf Niedermeier, and
Sebastian Wernicke:
Minimum membership set covering and the consecutive ones property.
In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory
(SWAT'06),
Riga, Latvia. July 2006.
Volume 4059 in Lecture Notes in Computer Science, pages 339–350, Springer
(original publication).
Journal version available.
-
Jens Gramm,
Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
Data reduction, exact, and heuristic algorithms for clique cover.
In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments
(ALENEX'06),
Miami, USA. January 2006.
Pages 86–94, SIAM
(original publication).
Journal version in preparation.
-
Jens Gramm,
Tzvika Hartman,
Till Nierhoff,
Roded Sharan, and
Till Tantau:
On the complexity of SNP block partitioning under the perfect phylogeny model.
In Proceedings of the 6th Workshop on Algorithms in Bioinformatics
(WABI'06),
Zürich, Switzerland. September 2006.
Volume 4175 in Lecture Notes in Computer Science, pages 92–102, Springer
(original publication).
Journal version available.
-
Jiong Guo,
Falk Hüffner,
Erhan Kenar,
Rolf Niedermeier, and
Johannes Uhlmann:
Complexity and exact algorithms for multicut.
In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science
(SOFSEM'06),
Merin, Czech Republic. January 2006.
Volume 3831 in Lecture Notes in Computer Science, pages 303–312, Springer
(original publication).
Journal version available.
-
Jiong Guo,
Rolf Niedermeier, and
Sebastian Wernicke:
Fixed-parameter tractability results for full-degree spanning tree and its dual.
In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation
(IWPEC'06),
Zürich, Switzerland. September 2006.
Volume 4169 in Lecture Notes in Computer Science, pages 203–214, Springer
(original publication).
- Michael Krüger and
Harald Hempel:
Inverse hamiltonian cycle and inverse 3-D matching are coNP-complete.
In Proceedings of the 17th Annual International Symposium on Algorithms and Computation
(ISAAC'06),
Kolkata, India. December 2006.
Volume 4288 in Lecture Notes in Computer Science, pages 243–252, Springer
(original publication).
-
Hannes Moser and
Dimitrios M. Thilikos:
Parameterized complexity of finding regular induced subgraphs.
In Proceedings of the 2nd Algorithms and Complexity in Durham
(ACiD'06),
Durham, England. September 2006.
Volume 7 in Texts in Algorithmics, pages 107–118, College Publications.
-
Harald Sack,
Uwe Krüger, and
Michael Dom:
A knowledge base on NP-complete decision problems and its application in bibliographic search.
XML-Tage 2006,
Berlin. September 2006.
|
| Journal articles |
-
Jochen Alber,
Nadja Betzler, and
Rolf Niedermeier:
Experiments on data reduction for optimal domination in networks.
Annals of Operations Research,
146(1): 105–117, 2006
(original publication).
-
Nadja Betzler,
Rolf Niedermeier, and
Johannes Uhlmann:
Tree decompositions of graphs: saving memory in dynamic programming.
Discrete Optimization,
3(3): 220–229, 2006
(original publication).
-
Michael Dom,
Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
Error compensation in leaf power problems.
Algorithmica,
44(4): 363–381, 2006
(original publication).
- Michael R. Fellows,
Jens Gramm, and
Rolf Niedermeier:
On the parameterized intractability of motif search problems.
Combinatorica,
26(2): 141–167, 2006
(original publication).
- Jens Gramm,
Jiong Guo, and
Rolf Niedermeier:
Parameterized intractability of distinguishing substring selection.
Theory of Computing Systems,
39(4): 545–560, 2006
(original publication).
- Jens Gramm,
Jiong Guo, and
Rolf Niedermeier:
Pattern matching for arc-annotated sequences.
ACM Transactions on Algorithms,
2(1): 44–65, 2006
(original publication).
-
Jiong Guo,
Jens Gramm,
Falk Hüffner,
Rolf Niedermeier, and
Sebastian Wernicke:
Compression-based fixed-parameter algorithms for Feedback Vertex Set and Edge Bipartization.
Journal of Computer and System Sciences,
72(8): 1386–1396, 2006
(original publication).
- Jiong Guo and
Rolf Niedermeier:
A fixed-parameter tractability result for multicommodity demand
flow in trees.
Information Processing Letters,
97(3): 109–114, 2006
(original publication).
- Jiong Guo and
Rolf Niedermeier:
Exact algorithms and applications for tree-like weighted set cover.
Journal of Discrete Algorithms,
4(4): 608–622, 2006
(original publication).
-
Sebastian Wernicke:
Efficient detection of network motifs.
IEEE/ACM Transactions
on Computational Biology and Bioinformatics,
3(4): 347–359, 2006
(original publication).
-
Sebastian Wernicke,
Jochen Alber,
Jens Gramm,
Jiong Guo, and
Rolf Niedermeier:
The computational complexity of avoiding forbidden submatrices by row deletions.
International Journal of
Foundations of Computer Science,
17(6): 1467–1484, 2006
(original publication).
- Sebastian Wernicke and
Florian Rasche:
FANMOD: a tool for fast network motif detection.
Bioinformatics,
22(9): 1152–1153, 2006
(original publication).
|
| Books |
|
| Theses |
-
Nadja Betzler:
Steiner Tree Problems in the Analysis of Biological Networks.
Diplomarbeit, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, 2006.
- Matthias Brosemann:
Matrixrobustheit: Algorithmen, Komplexität und Anwendung zur Netzwerküberwachung
(Matrix robustness: algorithms, complexity and an application in network observability).
Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2006.
- Alexander Fanghänel:
Das Problem Multipoint Relay – Komplexität und Algorithmen
(The multipoint relay problem—complexity and algorithms).
Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2006.
- Jiong Guo:
Algorithm Design Techniques for Parameterized Graph Modification Problems.
PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2006.
- Michael Schnupp:
Broadcast Domination with Flexible Powers.
Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2006.
- Sebastian Wernicke:
Combinatorial Algorithms to Cope with the Complexity of Biological Networks.
PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2006.
|
| 2005
| | Conference articles |
- Michael Dom,
Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
Extending the tractability border for closest leaf powers.
In Proceedings of the 31st International Workshop on
Graph-Theoretic Concepts in Computer Science
(WG'05),
Metz, France. June 2005.
Volume 3787 in Lecture Notes in Computer Science, pages 397–408, Springer
(original publication).
Journal version available.
- Michael Dom,
Jiong Guo,
and Rolf Niedermeier:
Bounded degree closest k-tree power is NP-complete.
In Proceedings of the 11th International Computing and Combinatorics Conference
(COCOON'05),
Kunming, China. August 2005.
Volume 3595 in Lecture Notes in Computer Science, pages 757–766, Springer
(original publication).
- Stefan Eckhardt,
Sven Kosub,
Moritz G. Maaß,
Hanjo Täubig, and
Sebastian Wernicke:
Combinatorial network abstraction by trees and distances.
In Proceedings of the 16th Annual International Symposium on Algorithms and Computation
(ISAAC'05),
Sanya, China. December 2005.
Volume 3827 in Lecture Notes in Computer Science, pages 1100–1109, Springer
(original publication).
Journal version available.
- Jiong Guo,
Jens Gramm,
Falk Hüffner,
Rolf Niedermeier, and
Sebastian Wernicke:
Improved fixed-parameter algorithms for two feedback set problems.
In Proceedings of the 9th Workshop on Algorithms and Data Structures
(WADS'05),
Waterloo, Canada. August 2005.
Volume 3608 in Lecture Notes in Computer Science, pages 158–168, Springer
(original publication).
Journal version available.
- Jiong Guo,
Rolf Niedermeier, and
Daniel Raible:
Improved algorithms and complexity results for power domination in graphs.
In Proceedings of the 15th International Symposium on
Fundamentals of Computation Theory
(FCT'05),
Lübeck, Germany. August 2005.
Volume 3623 in Lecture Notes in Computer Science, pages 172–184, Springer
(original publication).
Journal version in preparation.
- Jiong Guo,
Rolf Niedermeier, and
Sebastian Wernicke:
Parameterized complexity of generalized vertex cover problems.
In Proceedings of the 9th Workshop on Algorithms and Data Structures
(WADS'05),
Waterloo, Canada. August 2005.
Volume 3608 in Lecture Notes in Computer Science, pages 36–48, Springer
(original publication).
Journal version available.
- Falk Hüffner:
Algorithm engineering for optimal graph bipartization.
In Proceedings of the 4th International Workshop on Efficient and
Experimental Algorithms
(WEA'05),
Santorini Island, Greece. May 2005.
Volume 3503 in Lecture Notes in Computer Science, pages 240–252, Springer
(original publication).
Journal version available.
- Sebastian Wernicke:
A faster algorithm for detecting network motifs.
In Proceedings of the 5th Workshop on Algorithms in Bioinformatics
(WABI'05),
Mallorca, Spain. October 2005.
Volume 3692 in Lecture Notes in Bioinformatics, pages 165–177, Springer
(original publication).
Journal version available.
|
| Journal articles |
- Jochen Alber,
Frederic Dorn, and
Rolf Niedermeier:
Experimental evaluation of a tree decomposition based algorithm for
Vertex Cover on planar graphs.
Discrete Applied Mathematics,
145(2): 219–231, 2005
(original publication).
- Jochen Alber,
Hongbing Fan,
Michael R. Fellows,
Henning Fernau,
Rolf Niedermeier,
Frances A. Rosamond, and
Ulrike Stege:
A refined search tree technique for Dominating Set on planar graphs.
Journal of Computer and System Sciences,
71(4):385–405, 2005
(original publication).
- Jens Gramm,
Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
Graph-modeled data clustering: Exact algorithms for clique generation.
Theory of Computing Systems,
38(4):373–392, 2005
(original publication).
- Jiong Guo and
Rolf Niedermeier:
Fixed-parameter tractability and data reduction for multicut in trees.
Networks,
46(3):124–135, 2005
(original publication).
- Edith Hemaspaandra,
Lane A. Hemaspaandra, and
Harald Hempel:
Extending downward collapse from 1-versus-2 queries to
m-versus-m+1 queries.
SIAM Journal on Computing,
34(6):1352–1369, 2005
(original publication).
-
Edith Hemaspaandra,
Lane A. Hemaspaandra, and
Harald Hempel:
All superlinear inverse schemes are coNP-hard.
Theoretical Computer Science,
345(2–3):345–358, 2005
(original publication).
- Roded Sharan,
Jens Gramm,
Amir Ben-Dor, and
Zohar Yakhini:
Multiplexing schemes for generic SNP genotyping assays.
Journal of Computational Biology,
12(5):514–533, 2005
(original publication).
|
| Theses |
|
| 2004
| | Conference articles |
-
Nadja Betzler,
Rolf Niedermeier, and
Johannes Uhlmann:
Tree decompositions of graphs: saving memory in dynamic programming.
In Proceedings of the Cologne Twente Workshop on Graphs and
Combinatorial Optimization
(CTW'04),
Milano, Italy. May/June 2004.
Journal version available.
- Hans L. Bodlaender,
Celina M. Herrera de Figueiredo,
Marisa Gutierrez,
Ton Kloks, and
Rolf Niedermeier:
Simple Max-Cut for split-indifference graphs and graphs with few P4's.
In Proceedings of the 3rd Workshop on Efficient and Experimental Algorithms
(WEA'04),
Angra dos Reis, Rio de Janeiro, Brazil. May 2004.
Volume 3059 in Lecture Notes in Computer Science, pages 87–99, Springer
(original publication).
- Michael Dom,
Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
Error compensation in leaf root problems.
In Proceedings of the 15th Annual International Symposium on
Algorithms and Computation
(ISAAC'04),
Hong Kong, China. December 2004.
Volume 3341 in Lecture Notes in Computer Science, pages 389–401, Springer
(original publication).
Journal version available.
- Jens Gramm:
A polynomial-time algorithm for the matching of crossing contact-map patterns.
In Proceedings of the 4th International Workshop on Algorithms in Bioinformatics
(WABI'04),
Bergen, Norway. September 2004.
Volume 3240 in Lecture Notes in Bioinformatics, pages 38–49, Springer
(original publication).
Journal version available.
- Jens Gramm,
Till Nierhoff, and
Till Tantau:
Perfect path phylogeny haplotyping with missing data is fixed-parameter tractable.
In Proceedings of the International Workshop on Parameterized and Exact Computation
(IWPEC'04),
Bergen, Norway. September 2004.
Number 3162 in Lecture Notes in Computer Science, pages 174–186, Springer
(original publication).
- Jens Gramm,
Till Nierhoff,
Till Tantau, and
Roded Sharan:
On the complexity of haplotyping via perfect phylogeny.
In Proceedings of the
Second RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes,
Pittsburgh, USA. February 2004.
Lecture Notes in Bioinformatics, Springer.
- Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
A structural view on parameterizing problems: distance from triviality.
In Proceedings of the International Workshop on Parameterized and Exact Computation
(IWPEC'04),
Bergen, Norway. September 2004.
Volume 3162 in Lecture Notes in Computer Science, pages 162–173, Springer
(original publication).
- Edith Hemaspaandra,
Lane A. Hemaspaandra, and
Harald Hempel:
All superlinear inverse schemes are coNP-hard.
In Proceedings of the 29th International Symposium on Mathematical Foundations of
Computer Science
(MFCS'04),
Prague, Czech Republic. August 2004.
Volume 3153 in Lecture Notes in Computer Science, pages 368–379, Springer
(original publication).
Journal version available.
- Rolf Niedermeier:
Ubiquitous parameterization—invitation to fixed-parameter algorithms
(invited paper).
In Proceedings of the 29th International Symposium on Mathematical Foundations of
Computer Science
(MFCS'04),
Prague, Czech Republic. August 2004.
Volume 3153 in Lecture Notes in Computer Science, pages 84–103, Springer
(original publication).
- Sebastian Wernicke,
Jochen Alber,
Jens Gramm,
Jiong Guo, and
Rolf Niedermeier:
Avoiding forbidden submatrices by row deletions.
In Proceedings of the 30th Conference on Current Trends in Theory and Practice
of Informatics
(SOFSEM'04),
Měřín, Czech Republic. January 2004.
Volume 2932 in Lecture Notes in Computer Science, pages 349–360, Springer
(original publication).
Journal version available.
|
| Journal articles |
- Jochen Alber,
Michael R. Fellows and
Rolf Niedermeier:
Polynomial time data reduction for Dominating Set.
Journal of the ACM,
51(3): 363–384, 2004
(original publication).
- Jochen Alber,
Henning Fernau, and
Rolf Niedermeier:
Parameterized complexity: exponential speed-up for planar graph problems.
Journal of Algorithms, 52(1):26–56, 2004
(original publication).
- Jochen Alber,
Jens Gramm,
Jiong Guo, and
Rolf Niedermeier:
Computing the similarity of two sequences with nested arc annotations.
Theoretical Computer Science,
312(2–3): 337–358, 2004
(original publication).
-
Jens Gramm:
A polynomial-time algorithm for the matching of crossing contact-map patterns.
IEEE/ACM Transactions on Computational Biology and Bioinformatics,
1(4):171–180, 2004
(original publication).
- Jens Gramm,
Jiong Guo,
Falk Hüffner, and
Rolf Niedermeier:
Automated generation of search tree algorithms for hard graph
modification problems.
Algorithmica,
39(4):321–347, 2004
(original publication).
- Lane A. Hemaspaandra,
Harald Hempel, and
Arfst Nickelsen:
Algebraic properties for selector functions.
SIAM Journal on Computing,
33(6):1309–1337, 2004
(original publication).
|
Note: Some of the publications are © Springer-Verlag and other publishers.
|
Publications