Peter Rossmanith

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

Kernelization using structural parameters on sparse graph classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application.

[BibT_eX]

[DOI]

CoRR, 2017

An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

What One Has to Know When Attacking P vs. NP (Extended Abstract).

[BibT_eX]

[DOI]

Juraj Hromkovic

Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016

Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Are there any good digraph width measures?

[BibT_eX]

[DOI]

J. Comb. Theory B, 2016

Fixed-parameter algorithms for vertex cover P3.

[BibT_eX]

[DOI]

Discret. Optim., 2016

Width, depth and space.

[BibT_eX]

[DOI]

Li-Hsuan Chen

Felix Reidl

CoRR, 2016

2014

The online knapsack problem: Advice and randomization.

[BibT_eX]

[DOI]

Dennis Komm

Richard Královic

Theor. Comput. Sci., 2014

Lower bounds on the complexity of MSO1 model-checking.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

Exact algorithms for problems related to the densest k-set problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

Digraph width measures in parameterized algorithmics.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2014

Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

Practical algorithms for MSO model-checking on tree-decomposable graphs.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2014

Overlapping Communities in Social Networks.

[BibT_eX]

[DOI]

CoRR, 2014

Structural Sparsity of Complex Networks: Random Graph Models and Linear Algorithms.

[BibT_eX]

[DOI]

Erik D. Demaine

Felix Reidl

Blair D. Sullivan

CoRR, 2014

Finite Integer Index of Pathwidth and Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

A Faster Parameterized Algorithm for Treedepth.

[BibT_eX]

[DOI]

Felix Reidl

Konstanty Junosza-Szaniawski

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Fast exact algorithm for L(2, 1)-labeling of graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Testing consistency of quartet topologies: a parameterized approach.

[BibT_eX]

[DOI]

Chuang-Chieh Lin

Inf. Process. Lett., 2013

Recognition of probe distance-hereditary graphs.

[BibT_eX]

[DOI]

Ling-Ju Hung

Discret. Appl. Math., 2013

2012

Linear Kernels on Graphs Excluding Topological Minors

[BibT_eX]

[DOI]

CoRR, 2012

Lower Bounds on the Complexity of MSO_1 Model-Checking.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

On the Advice Complexity of the Knapsack Problem.

[BibT_eX]

[DOI]

Dennis Komm

Richard Královic

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

On the Power of Randomness versus Advice in Online Computation.

[BibT_eX]

[DOI]

Proceedings of the Languages Alive, 2012

Evaluation of an MSO-Solver.

[BibT_eX]

[DOI]

Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, 2012

2011

An exact algorithm for the Maximum Leaf Spanning Tree problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

A Property Tester for Tree-Likeness of Quartet Topologies.

[BibT_eX]

[DOI]

Chuang-Chieh Lin

Theory Comput. Syst., 2011

Breaking the 2n-barrier for Irredundance: Two lines of attack.

[BibT_eX]

[DOI]

Daniel Binkele-Raible

Jakub Onufry Wojtaszczyk

J. Discrete Algorithms, 2011

Courcelle's theorem - A game-theoretic approach.

[BibT_eX]

[DOI]

Discret. Optim., 2011

Lower Bounds on the Complexity of MSO1 Model-Checking

[BibT_eX]

[DOI]

CoRR, 2011

Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory

[BibT_eX]

[DOI]

CoRR, 2011

A New Algorithm for Finding Trees with Many Leaves.

[BibT_eX]

[DOI]

Algorithmica, 2011

Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory - (Extended Abstract).

[BibT_eX]

[DOI]

Konstanty Junosza-Szaniawski

Proceedings of the Theory and Applications of Models of Computation, 2011

Fast Exact Algorithm for L(2, 1)-Labeling of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2011

Simulated Annealing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms Unplugged, 2011

2010

New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem.

[BibT_eX]

[DOI]

Chuang-Chieh Lin

Theory Comput. Syst., 2010

A Parameterized Route to Exact Puzzles: Breaking the 2n-Barrier for Irredundance.

[BibT_eX]

[DOI]

Daniel Binkele-Raible

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

Probe Distance-Hereditary Graphs.

[BibT_eX]

[DOI]

Ling-Ju Hung

Proceedings of the Theory of Computing 2010, 2010

2009

Reoptimization of Steiner trees: Changing the terminal set.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

Breaking the 2^n-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles

[BibT_eX]

[DOI]

CoRR, 2009

A Fine-grained Analysis of a Simple Independent Set Algorithm.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution.

[BibT_eX]

[DOI]

Johan M. M. van Rooij

Hans L. Bodlaender

Proceedings of the Algorithms, 2009

Breaking Anonymity by Learning a Unique Minimum Hitting Set.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2009

2008

Simulated Annealing.

[BibT_eX]

[DOI]

Proceedings of the Taschenbuch der Algorithmen, 2008

Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover.

[BibT_eX]

[DOI]

Stefan Richter

Theory Comput. Syst., 2008

Improved Upper Bounds for Partial Vertex Cover.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

2007

Dynamic Programming for Minimum Steiner Trees.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Partial vs. Complete Domination: t-Dominating Set.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007

2006

Parameterized power domination complexity.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2006

Divide-and-Color.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

A Faster Algorithm for the Steiner Tree Problem.

[BibT_eX]

[DOI]

Stefan Richter

Proceedings of the STACS 2006, 2006

Intuitive Algorithms and t-Vertex Cover.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants.

[BibT_eX]

[DOI]

Stefan Richter

Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

2005

Algorithms Based on the Treewidth of Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

On the Parameterized Complexity of Exact Satisfiability Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2003

An efficient fixed-parameter algorithm for 3-Hitting Set.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2003

On efficient fixed-parameter algorithms for weighted vertex cover.

[BibT_eX]

[DOI]

J. Algorithms, 2003

Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2003

Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems.

[BibT_eX]

[DOI]

Jens Gramm

Algorithmica, 2003

2001

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Stochastic Finite Learning of the Pattern Languages.

[BibT_eX]

[DOI]

Thomas Zeugmann

Mach. Learn., 2001

Exact Solutions for CLOSEST STRING and Related Problems.

[BibT_eX]

[DOI]

Jens Gramm

Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

2000

New Upper Bounds for Maximum Satisfiability.

[BibT_eX]

[DOI]

J. Algorithms, 2000

A general method to speed up fixed-parameter-tractable algorithms.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

An efficient automata approach to some problems on context-free grammars.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

A Uniform Framework for Problems on Context-Free Grammars.

[BibT_eX]

Javier Esparza

Stefan Schwoon

Bull. EATCS, 2000

Efficient Algorithms for Model Checking Pushdown Systems.

[BibT_eX]

[DOI]

Proceedings of the Computer Aided Verification, 12th International Conference, 2000

1999

Optimal Deterministic Sorting and Routing on Grids and Tori with Diagonals.

[BibT_eX]

[DOI]

Algorithmica, 1999

Upper Bounds for Vertex Cover Further Improved.

[BibT_eX]

[DOI]

Proceedings of the STACS 99, 1999

New Upper Bounds for MaxSat.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

Learning from Random Text.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

1998

Unambiguous Computations and Locally Definable Acceptance Types.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Learning k-Variable Pattern Languages Efficiently Stochastically Finite on Average from Positive Data.

[BibT_eX]

[DOI]

Thomas Zeugmann

Proceedings of the Grammatical Inference, 4th International Colloquium, 1998

1997

Expressing Uniformity via Oracles.

[BibT_eX]

[DOI]

Carsten Damm

Markus Holzer

Theory Comput. Syst., 1997

An Automata Approach to Some Problems on Context-Free Grammars.

[BibT_eX]

[DOI]

Javier Esparza

Proceedings of the Foundations of Computer Science: Potential - Theory, 1997

1995

Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits

[BibT_eX]

[DOI]

Inf. Comput., May, 1995

On Optimal Orow-Pram Algorithms for Computing Recursively Defined Functions.

[BibT_eX]

[DOI]

Parallel Process. Lett., 1995

Optimal Average Case Sorting on Arrays.

[BibT_eX]

[DOI]

Proceedings of the STACS 95, 1995

PRAM's Towards Realistic Parallelism: BRAM's.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

1994

Characterizations of memory access for PRAM's and bounds on the time complexity of Boolean functions.

[BibT_eX]

[DOI]

PhD thesis, 1994

Unambiguous Polynomial Hierarchies and Exponential Size.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Faster sorting and routing on grids with diagonals

[BibT_eX]

[DOI]

Manfred Kunde

Forschungsberichte, TU Munich, 1993

Extended Locally Definable Acceptance Types (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the STACS 93, 1993

On the Power of Reading and Writing Simultaneously in Parallel Computation.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Deterministic OL Languages are of Very Low Complexity: DOL is in AC0.

[BibT_eX]

Proceedings of the Developments in Language Theory, 1993

1992

Optimal parallel algorithms for computing recursively defined functions

[BibT_eX]

[DOI]

Forschungsberichte, TU Munich, 1992

Oberservation on log(n) Time Parallel Recognition of Unambiguous cfl's.

[BibT_eX]

[DOI]

Wojciech Rytter

Inf. Process. Lett., 1992

Parallel Recognition and Ranking of Context-Free Languages.

[BibT_eX]

[DOI]

Wojciech Rytter

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

The Emptiness Problem for Intersections of Regular Languages.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the LATIN '92, 1992

1991

Unambiguity and Fewness for Logarithmic Space.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990

Uniform circuits and exclusive read PRAMs

[BibT_eX]

[DOI]

Inga Niepel

Forschungsberichte, TU Munich, 1990

Unambiguous simulations of auxiliary pushdown automata and circuits

[BibT_eX]

[DOI]

Forschungsberichte, TU Munich, 1990

The owner concept for PRAMs

[BibT_eX]

[DOI]

Forschungsberichte, TU Munich, 1990

Two results on unambiguous circuits

[BibT_eX]

[DOI]

Forschungsberichte, TU Munich, 1990

Characterizing Unambiguous Augmented Pushdown Automata by Circuits.

[BibT_eX]

[DOI]