Peter Rossmanith

According to our database1, Peter Rossmanith authored at least 96 papers between 1990 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2019
Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs.
J. Comput. Syst. Sci., 2019

2018
MFCS 2019 - First Call for Papers.
Bulletin of the EATCS, 2018

Moderately exponential time algorithms for the maximum bounded-degree-1 set problem.
Discrete Applied Mathematics, 2018

Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming.
Algorithms, 2018

Local Structure Theorems for Erdős-Rényi Graphs and Their Algorithmic Applications.
Proceedings of the SOFSEM 2018: Theory and Practice of Computer Science - 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29, 2018

On the Advice Complexity of Online Edge- and Node-Deletion Problems.
Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017
An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem.
Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

What One Has to Know When Attacking P vs. NP (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016
Fixed-parameter algorithms for vertex cover P3.
Discrete Optimization, 2016

2014
The online knapsack problem: Advice and randomization.
Theor. Comput. Sci., 2014

Lower bounds on the complexity of MSO1 model-checking.
J. Comput. Syst. Sci., 2014

Exact algorithms for problems related to the densest k-set problem.
Inf. Process. Lett., 2014

Digraph width measures in parameterized algorithmics.
Discrete Applied Mathematics, 2014

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

Practical algorithms for MSO model-checking on tree-decomposable graphs.
Computer Science Review, 2014

Finite Integer Index of Pathwidth and Treewidth.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

A Faster Parameterized Algorithm for Treedepth.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Fast exact algorithm for L(2, 1)-labeling of graphs.
Theor. Comput. Sci., 2013

Testing consistency of quartet topologies: a parameterized approach.
Inf. Process. Lett., 2013

Recognition of probe distance-hereditary graphs.
Discrete Applied Mathematics, 2013

Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Kernelization Using Structural Parameters on Sparse Graph Classes.
Proceedings of the Algorithms - ESA 2013, 2013

2012
Lower Bounds on the Complexity of MSO_1 Model-Checking.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

On the Advice Complexity of the Knapsack Problem.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

On the Power of Randomness versus Advice in Online Computation.
Proceedings of the Languages Alive, 2012

Evaluation of an MSO-Solver.
Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, 2012

2011
A Property Tester for Tree-Likeness of Quartet Topologies.
Theory Comput. Syst., 2011

Breaking the 2n-barrier for Irredundance: Two lines of attack.
J. Discrete Algorithms, 2011

Courcelle's theorem - A game-theoretic approach.
Discrete Optimization, 2011

Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory - (Extended Abstract).
Proceedings of the Theory and Applications of Models of Computation, 2011

Fast Exact Algorithm for L(2, 1)-Labeling of Graphs.
Proceedings of the Theory and Applications of Models of Computation, 2011

Simulated Annealing.
Proceedings of the Algorithms Unplugged, 2011

2010
Are There Any Good Digraph Width Measures?
Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

A Parameterized Route to Exact Puzzles: Breaking the 2n-Barrier for Irredundance.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

Probe Distance-Hereditary Graphs.
Proceedings of the Theory of Computing 2010, 2010

2009
Reoptimization of Steiner trees: Changing the terminal set.
Theor. Comput. Sci., 2009

A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms.
SIAM J. Discrete Math., 2009

On Digraph Width Measures in Parameterized Algorithmics.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

An Exact Algorithm for the Maximum Leaf Spanning Tree Problem.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

A Fine-grained Analysis of a Simple Independent Set Algorithm.
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.
Proceedings of the Algorithms, 2009

Breaking Anonymity by Learning a Unique Minimum Hitting Set.
Proceedings of the Computer Science, 2009

2008
Simulated Annealing.
Proceedings of the Taschenbuch der Algorithmen, 2008

Improved Upper Bounds for Partial Vertex Cover.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem.
Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

A New Algorithm for Finding Trees with Many Leaves.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007
Dynamic Programming for Minimum Steiner Trees.
Theory Comput. Syst., 2007

Partial vs. Complete Domination: t-Dominating Set.
Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007

2006
Parameterized power domination complexity.
Inf. Process. Lett., 2006

Divide-and-Color.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

A Faster Algorithm for the Steiner Tree Problem.
Proceedings of the STACS 2006, 2006

Intuitive Algorithms and t-Vertex Cover.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover.
Proceedings of the Computer Science, 2006

Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants.
Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

2005
Algorithms Based on the Treewidth of Sparse Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

On the Parameterized Complexity of Exact Satisfiability Problems.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2003
An efficient fixed-parameter algorithm for 3-Hitting Set.
J. Discrete Algorithms, 2003

Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
Discrete Applied Mathematics, 2003

Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems.
Algorithmica, 2003

2001
Stochastic Finite Learning of the Pattern Languages.
Machine Learning, 2001

Exact Solutions for CLOSEST STRING and Related Problems.
Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

2000
New Upper Bounds for Maximum Satisfiability.
J. Algorithms, 2000

A general method to speed up fixed-parameter-tractable algorithms.
Inf. Process. Lett., 2000

An efficient automata approach to some problems on context-free grammars.
Inf. Process. Lett., 2000

New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT
Electronic Colloquium on Computational Complexity (ECCC), 2000

A Uniform Framework for Problems on Context-Free Grammars.
Bulletin of the EATCS, 2000

On Efficient Fixed Parameter Algorithms for WEIGHTED VERTEX COVER.
Proceedings of the Algorithms and Computation, 11th International Conference, 2000

Efficient Algorithms for Model Checking Pushdown Systems.
Proceedings of the Computer Aided Verification, 12th International Conference, 2000

1999
Optimal Deterministic Sorting and Routing on Grids and Tori with Diagonals.
Algorithmica, 1999

Upper Bounds for Vertex Cover Further Improved.
Proceedings of the STACS 99, 1999

New Upper Bounds for MaxSat.
Proceedings of the Automata, 1999

Learning from Random Text.
Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

1998
Unambiguous Computations and Locally Definable Acceptance Types.
Theor. Comput. Sci., 1998

Learning k-Variable Pattern Languages Efficiently Stochastically Finite on Average from Positive Data.
Proceedings of the Grammatical Inference, 4th International Colloquium, 1998

1997
Expressing Uniformity via Oracles.
Theory Comput. Syst., 1997

An Automata Approach to Some Problems on Context-Free Grammars.
Proceedings of the Foundations of Computer Science: Potential - Theory, 1997

Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1995
Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits
Inf. Comput., May, 1995

Expressing Uniformity via Oracles
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

On Optimal Orow-Pram Algorithms for Computing Recursively Defined Functions.
Parallel Processing Letters, 1995

Optimal Average Case Sorting on Arrays.
Proceedings of the STACS 95, 1995

PRAM's Towards Realistic Parallelism: BRAM's.
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.
PhD thesis, 1994

Faster Sorting and Routing on Grids with Diagonals.
Proceedings of the STACS 94, 1994

Unambiguous Polynomial Hierarchies and Exponential Size.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993
Extended Locally Definable Acceptance Types (Extended Abstract).
Proceedings of the STACS 93, 1993

On the Power of Reading and Writing Simultaneously in Parallel Computation.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Deterministic OL Languages are of Very Low Complexity: DOL is in AC0.
Proceedings of the Developments in Language Theory, 1993

1992
Oberservation on log(n) Time Parallel Recognition of Unambiguous cfl's.
Inf. Process. Lett., 1992

Parallel Recognition and Ranking of Context-Free Languages.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

The Emptiness Problem for Intersections of Regular Languages.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits (Extended Abstract).
Proceedings of the LATIN '92, 1992

1991
The Owner Concept for PRAMs.
Proceedings of the STACS 91, 1991

Uniform Circuits and Exclusive Read PRAMs.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

Unambiguity and Fewness for Logarithmic Space.
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990
Characterizing Unambiguous Augmented Pushdown Automata by Circuits.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990


  Loading...