| 2011
| | Conference articles |
-
Britta Dorn,
Falk Hüffner,
Dominikus Krüger,
Rolf Niedermeier, and
Johannes Uhlmann:
Exploiting bounded signal flow for graph orientation based on cause–effect pairs.
In Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems
(TAPAS '11),
Rome, Italy. April 2011.
Volume 6595 in Lecture Notes in Computer Science, pages 104–115, Springer
(original publication).
-
Christian Komusiewicz and
Johannes Uhlmann:
Alternative Parameterizations for Cluster Editing.
In Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science
(SOFSEM'11),
Nový Smokovec, Slovakia, January 2011.
-
Nadja Betzler,
Robert Bredereck,
Rolf Niedermeier, and
Johannes Uhlmann:
On Making a Distinguished Vertex Minimum Degree by Vertex Deletion
In Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science
(SOFSEM'11),
Nový Smokovec, Slovakia, January 2011.
|
| Book chapters |
|
| 2010
| | Conference articles |
-
Nadja Betzler,
Robert Bredereck, and
Rolf Niedermeier:
Partial Kernelization for Rank Aggregation: Theory and Experiments.
In Proceedings of the International Symposium on Parameterized and Exact Computation
(IPEC'10), Chennai, India, December 2010.
-
Yoram Bachrach,
Nadja Betzler, and
Piotr Faliszewski:
Probabilistic Possible Winner Determination.
In Proceedings of the 24th AAAI Conference on Artificial Intelligence
(AAAI'10), Atlanta, Georgia, USA, July 2010. Pages 697–702, (original publication).
-
Nadja Betzler:
On Problem Kernels for Possible Winner Determination Under the k-Approval Protocol.
In Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science
(MFCS'10), Brno, Czech Republic, August 2010. Volume 6281 in
Lecture Notes in Computer Science, pages 114–125,
Springer (original publication).
- Nadja Betzler,
Jiong Guo,
Christian Komusiewicz, and
Rolf Niedermeier:
Average Parameterization and Partial Kernelization for Computing Medians.
In Proceedings of the 9th Latin American
Theoretical Informatics Symposium
(LATIN'10),
Oaxaca, México, April 2010. Volume 6034 in
Lecture Notes in Computer Science, pages
60–71, Springer (original publication).
- René van Bevern,
Christian Komusiewicz,
Hannes Moser, and
Rolf
Niedermeier:
Measuring
Indifference: Unit Interval Vertex
Deletion.
In Proceedings of the
36th International Workshop on Graph Theoretic
Concepts in Computer Science
(WG'10),
Zarós (Crete), Greece, June
2010. Volume 6410 in Lecture Notes in Computer
Science, pages 232–243, Springer (original publication).
- René
van Bevern,
Hannes Moser, and
Rolf Niedermeier:
Kernelization
through tidying—a case study based on s-plex cluster
vertex deletion.
In Proceedings of the 9th Latin
American Theoretical Informatics Symposium
(LATIN'10),
Oaxaca, México, April 2010. Volume 6034 in Lecture Notes in
Computer Science, pages
528–539, Springer (original publication).
- Frederic Dorn,
Hannes Moser,
Rolf Niedermeier, and
Mathias Weller:
Efficient Algorithms for Eulerian Extension.
In Proceedings of the 36th International Workshop on Graph Theoretic
Concepts in Computer Science
(WG'10),
Zarós (Crete), Greece, June
2010. Volume 6410 in Lecture Notes in Computer
Science, pages 232–243, Springer (original publication).
-
Extended Islands of Tractability for Parsimony Haplotyping.
In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching
(CPM'10), New York, USA, June 2010. Volume 6129 in Lecture Notes in Computer Science, pages 214–226, Springer (original publication).
- Jiong Guo,
Sepp Hartung,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
Exact Algorithms and Experiments for Hierarchical Tree Clustering.
In Proceedings of the 24th AAAI Conference on Artificial Intelligence
(AAAI'10), Atlanta, GA, USA, July 2010 (original publication).
- :
Incremental List Coloring of Graphs,
Parameterized by Conservation.
In Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC'10), Prague, Czech Republic, June 2010.
Volume 6108 in Lecture Notes in Computer Science, pages 258–270, Springer (original publication).
- André
Nichterlein,
Rolf Niedermeier,
Johannes Uhlmann, and
Mathias Weller:
On Tractable Cases of Target Set Selection.
In Proceedings of the 21st International Symposium on Algorithms and Computation
(ISAAC'10), Jeju Island, Korea, December 2010.
- Rolf Niedermeier:
Reflections on Multivariate Algorithmics and Problem Parameterization.
In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science
(STACS'10), Nancy, France, March 2010.
Volume 5 in Leibniz International Proceedings in Informatics (LIPIcs), pages 17–32, Schloss Dagstuhl–Leibniz-Zentrum für Informatik (original publication).
-
:
Two-Layer Planarization Parameterized by Feedback Edge Set.
In Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC'10), Prague, Czech Republic, June 2010. Volume 6108 in Lecture Notes in Computer Science, pages 431–442, Springer (original publication).
|
| Journal articles |
-
Nadja Betzler and
Britta Dorn:
Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
Journal of Computer and System Sciences 76(8): 812–836, 2010 (original publication).
-
Nadja Betzler,
Jiong Guo, and
Rolf Niedermeier:
Parameterized Computational Complexity of Dodgson and Young Elections.
Information and Computation 208(2): 165–177, 2010
(original publication).
-
Michael Dom,
Jiong Guo, and
Rolf Niedermeier:
Approximation and Fixed-Parameter Algorithms for
Consecutive Ones Submatrix Problems.
Journal of Computer and System Sciences 76(3-4): 204–221
(original publication).
- Michael Dom,
Jiong Guo,
Falk Hüffner,
Rolf Niedermeier, and
Anke Truss:
Fixed-parameter tractability results for feedback set problems in tournaments.
Journal of Discrete Algorithms 8(1):76–86, 2010
(original publication).
-
Falk Hüffner,
Nadja Betzler, and
Rolf Niedermeier:
Separator-based data reduction for signed graph balancing.
Journal of Combinatorial Optimization 20(4):335–360, 2010
(original publication).
-
Jiong Guo,
Rolf Niedermeier,
Sebastian Wernicke:
Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual.
Networks 56(2):116–130,
(original publication).
-
Jiong Guo and
Johannes Uhlmann:
Kernelization and Complexity Results for Connectivity Augmentation Problems.
Networks 56(2):131–142, 2010
(original publication).
-
Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Fixed-parameter algorithms for cluster vertex deletion.
Theory of Computing Systems 47(1):196–217, 2010
(original publication).
|
| Journal articles (to appear) |
-
Nadja Betzler,
René van Bevern,
Michael R. Fellows,
Christian Komusiewicz, and
Rolf Niedermeier:
Parameterized Algorithmics for Finding Connected Motifs in Biological Networks.
IEEE/ACM Transactions on Computational Biology and Bioinformatics.
Accepted for publication, September 2010.
-
Nadja Betzler,
Jiong Guo,
Christian Komusiewicz, and
Rolf Niedermeier:
Average Parameterization and Partial Kernelization for Computing Medians.
Journal of Computer and System Sciences.
Accepted for publication, July 2010 (original publication).
-
Michael Dom,
Michael R. Fellows,
Frances A. Rosamond, and
Somnath Sikdar:
The parameterized complexity of stabbing rectangles.
Algorithmica.
Accepted for publication (original publication).
-
Michael R. Fellows,
Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
Graph-based data clustering with overlaps.
Discrete Optimization.
Accepted for publication, September 2010 (original publication).
-
Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
A more relaxed model for graph-based data clustering: s-plex cluster editing.
SIAM Journal on Discrete Mathematics.
Accepted for publication, July 2010.
- Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann:
Deconstructing
Intractability – A Multivariate Complexity Analysis of
Interval Constrained Coloring.
Journal of Discrete Algorithms.
Accepted for publication, July 2010 (original publication).
|
| Book chapters |
|
| Theses |
|
| 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.
Volume 5457 in Lecture Notes in Computer Science, pages 141–151, Springer (original publication).
-
Nadja Betzler and Britta Dorn:
Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules.
In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science
(MFCS'09),
Novy Smokovec, Slovakia, August 2009.
Volume 5734 in Lecture Notes in Computer Science, pages 124–136, Springer (original publication).
-
Nadja Betzler,
Susanne Hemmann, and
Rolf Niedermeier:
A multivariate complexity analysis of
determining possible winners given incomplete votes.
In Proceedings of the 21st International Joint Conference on Artificial Intelligence
(IJCAI'09), pages 53-58
Pasadena, USA, July 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), pages 657–664, Budapest, Hungary, May 2009 (original publication).
-
Daniel Brügmann, Christian Komusiewicz, and
Hannes Moser:
On generating triangle-free graphs.
In Proceedings of the DIMAP Workshop on Algorithmic Graph Theory
(AGT'09),
Warwick, England, March 2009.
Electronic Notes in Discrete Mathematics 32, pages 51–58, Elsevier
(original publication).
-
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.
Volume 5431 in Lecture Notes in Computer Science, pages 298–309. Springer (original publication).
-
Michael Dom,
Daniel Lokshtanov, and
Saket Saurabh:
Incompressibility through colors and IDs.
In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming
(ICALP'09),
Rhodes, Greece, July 2009.
Volume 5555 in Lecture Notes in Computer Science, pages 378–389. Springer (original publication).
-
Rosa Enciso,
Michael R. Fellows,
Jiong Guo,
Iyad A. Kanj,
Frances A. Rosamond,
and Ondrej Suchý:
What makes equitable connected partition easy.
In Proceedings of the 4th International Workshop on Parameterized and Exact Computation
(IWPEC'09), Copenhagen, Denmark, September 2009.
Volume 5917 in Lecture Notes in Computer Science, pages 122–33. Springer (original publication).
-
Michael R. Fellows,
Jiong Guo,
and Iyad A. Kanj:
The parameterized complexity of some minimum label problems.
In Proceedings of the 35th International Workshop
on Graph-Theoretic Concepts in Computer Science
(WG'09),
Montpellier, France, June 2009.
Volume 5911 in Lecture Notes in Computer Science, pages 88–99. Springer (original publication).
-
Michael R. Fellows,
Jiong Guo,
Hannes Moser, and
Rolf Niedermeier:
A complexity dichotomy for finding disjoint solutions of vertex deletion problems.
In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science
(MFCS'09),
Novy Smokovec, Slovakia, August 2009.
Volume 5734 in Lecture Notes in Computer Science, pages 319–330, Springer (original publication).
-
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.
Dagstuhl Seminar Proceedings, pages 409–420,
Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI),
Schloss Dagstuhl, Germany
(original publication).
-
Michael R. Fellows,
Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
Graph-based data clustering with overlaps.
In Proceedings of the 15th International Computing and Combinatorics Conference
(COCOON'09),
Niagara Falls, USA, June 2009.
Volume 5609 in Lecture Notes in Computer Science, pages 516–526, Springer (original publication).
-
Jiong Guo:
Fixed-parameter algorithms for graph-modeled data clustering (invited paper).
In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation
(TAMC'09),
Changsha, China, May 2009.
Volume 5532 in Lecture Notes in Computer Science, pages 39–48, Springer (original publication).
-
Jiong Guo,
Iyad A. Kanj,
Christian Komusiewicz, and
Johannes Uhlmann:
Editing Graphs into Disjoint Unions of Dense Clusters.
In Proceedings of the 20th International Symposium on Algorithms and Computation
(ISAAC'09),
Hawaii, USA, December 2009.
Volume 5878 in Lecture Notes in Computer Science, pages 583–593. Springer (original publication).
-
Jiong Guo,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
A more relaxed model for graph-based data clustering: s-plex editing.
In Proceedings of the 5th International Conference on
Algorithmic Aspects in Information and Management
(AAIM'09),
San Francisco, USA, June 2009.
Volume 5564 in Lecture Notes in Computer Science, pages 226–239, Springer (original publication).
-
Jiong Guo, Rolf Niedermeier, and Ondrej Suchý:
Parameterized Complexity of Arc-Weighted Directed Steiner Problems.
In Proceedings of the 20th International Symposium on Algorithms and Computation
(ISAAC'09),
Hawaii, USA, December 2009.
Volume 5878 in Lecture Notes in Computer Science, pages 544–553. Springer (original publication).
-
Christian Komusiewicz, Rolf Niedermeier, and
Johannes Uhlmann:
Deconstructing intractability – a case study for interval constrained coloring.
In Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching
(CPM'09),
Lille, France, June 2009.
Volume 5577 in Lecture Notes in Computer Science, pages 207–220, Springer
(original publication).
-
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.
Volume 5404 in Lecture Notes in Computer Science, pages 401–412, Springer
(original publication).
-
Hannes Moser,
Rolf Niedermeier, and
Manuel Sorge:
Algorithms and experiments for clique relaxations—finding maximum s-plexes.
In Proceedings of the 8th International Symposium on Experimental Algorithms
(SEA'09),
Dortmund, Germany, June 2009.
Volume 5526 in Lecture Notes in Computer Science, pages 233–244, Springer
(original publication).
-
Mathias Weller,
Christian Komusiewicz,
Rolf Niedermeier, and
Johannes Uhlmann:
On making directed graphs transitive.
In Proceedings of the 11th Algorithms and Data Structures Symposium
(WADS'09),
Banff, Canada, August 2009.
Volume 5664 in Lecture Notes in Computer Science, pages 542–553. Springer (original publication).
Long version submitted to a journal.
|
| Journal articles |
-
Nadja Betzler,
Michael R. Fellows,
Jiong Guo,
Rolf Niedermeier, and
Frances A. Rosamond:
Fixed-Parameter Algorithms for Kemeny Rankings.
Theoretical Computer Science , 410(45):4554–4570, 2009
(original publication)
-
Nadja Betzler and Johannes Uhlmann:
Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems.
Theoretical Computer Science 410(52):5425-5442, 2009 (original publication)
-
Michael Dom:
Algorithmic Aspects of the Consecutive-Ones Property.
Bulletin of the European Association for Theoretical Computer Science,
98:27–59, 2009 (original publication).
-
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, 309(18):5610–5617, 2009
(original publication).
-
Jiong Guo:
A more effective linear kernelization for cluster editing.
Theoretical Computer Science, 410(8–10):718–726, 2009
(original publication).
-
Falk Hüffner:
Algorithm engineering for optimal graph bipartization.
Journal of Graph Algorithms and Applications, 13(2):77–98, 2009
(original publication).
-
Falk Hüffner:
Parametrisierte Ansätze für schwere Graphprobleme: Algorithmen und Experimente.
it – Information Technology, 51(3):171–174, 2009
(original publication).
-
Falk Hüffner,
Christian Komusiewicz,
Hannes Moser, and
Rolf Niedermeier:
Isolation concepts for clique enumeration: comparison and computational experiments.
Theoretical Computer Science, 410(52):5384–5397, 2009
(original publication).
-
Christian Komusiewicz,
Falk Hüffner,
Hannes Moser, and
Rolf Niedermeier:
Isolation concepts for efficiently enumerating dense subgraphs.
Theoretical Computer Science, 410(38–40):3640–3654, 2009
(original publication).
-
Hannes Moser and
Somnath Sikdar:
The parameterized complexity of the induced matching problem.
Discrete Applied Mathematics, 157(4):715–727, 2009
(original publication).
-
Hannes Moser and
Dimitrios M. Thilikos:
Parameterized complexity of finding regular induced subgraphs.
Journal of Discrete Algorithms,
7(2):181–190, 2009.
(original publication).
|
| Book chapters |
-
Jiong Guo,
Hannes Moser, and
Rolf Niedermeier:
Iterative Compression for Exactly Solving NP-Hard Minimization Problems.
In: Algorithmics of Large and Complex Networks,
Volume 5515 in Lecture Notes in Computer Science, pages 65–80, Springer, 2009 (original publication).
Note that this version of the document is slightly updated compared to the official LNCS version.
-
Falk Hüffner,
Rolf Niedermeier, and
Sebastian Wernicke:
Fixed-parameter algorithms for graph-modeled data clustering.
In:
Clustering Challenges in Biological Networks, chapter 1, pages 3–28,
World Scientific, 2009
(original publication).
|
| Theses |
- René van Bevern:
Graph-based data clustering:
a quadratic-vertex problem kernel for s-Plex Cluster Vertex
Deletion.
Studienarbeit, Institut für Informatik,
Friedrich-Schiller-Universität Jena, September 2009.
-
Hannes Moser:
Finding optimal solutions for covering and matching problems.
PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2009.
-
Alexander Schäfer:
Exact algorithms for s-club finding and related problems.
Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Dezember 2009.
| 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.
Updated version available.
-
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).
Note: After publication, we have been notified of a
problem in the proof of Theorem 4 that does not seem to be
easy to fix. Thus, we retract the results in Section 4.
-
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).
Journal version available.
-
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:
Parametrisierte Ansätze für schwere Graphprobleme: Algorithmen und Experimente
(Algorithms and Experiments for Parameterized Approaches to Hard Graph Problems).
In:
Ausgezeichnete Informatikdissertationen 2007,
volume D-8 in GI Lecture Notes in Informatics,
pages 151–160, GI, 2008.
-
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).
Journal version available.
-
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).
Journal version available.
-
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 available.
-
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