Hans L. Bodlaender

According to our database1, Hans L. Bodlaender authored at least 247 papers between 1985 and 2019.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
On exploring always-connected temporal graphs of small pathwidth.
Inf. Process. Lett., 2019

EATCS-IPEC Nerode Prize 2019 - Call for Nominations.
Bulletin of the EATCS, 2019

The Homogeneous Broadcast Problem in Narrow and Wide Strips II: Lower Bounds.
Algorithmica, 2019

The Homogeneous Broadcast Problem in Narrow and Wide Strips I: Algorithms.
Algorithmica, 2019

Parameterized Complexity of Conflict-Free Graph Coloring.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Stable Divisorial Gonality is in NP.
Proceedings of the SOFSEM 2019: Theory and Practice of Computer Science, 2019

Subgraph Isomorphism on Graph Classes that Exclude a Substructure.
Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2018
Recognizing Hyperelliptic Graphs in Polynomial Time.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

On the Exact Complexity of Polyomino Packing.
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

An ETH-Tight Exact Algorithm for Euclidean TSP.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Definability equals recognizability for k-outerplanar graphs and l-chordal partial k-trees.
Eur. J. Comb., 2017

Characterizing width two for variants of treewidth.
Discrete Applied Mathematics, 2017

The Homogeneous Broadcast Problem in Narrow and Wide Strips.
Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

On the Maximum Weight Minimal Separator.
Proceedings of the Theory and Applications of Models of Computation, 2017

Computing Treewidth on the GPU.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Improved Lower Bounds for Graph Embedding Problems.
Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016
Treewidth of Graphs.
Encyclopedia of Algorithms, 2016

Kernelization, Exponential Lower Bounds.
Encyclopedia of Algorithms, 2016

A ck n 5-Approximation Algorithm for Treewidth.
SIAM J. Comput., 2016

Exact Algorithms for Intervalizing Coloured Graphs.
Theory Comput. Syst., 2016

Robust Recoverable Path Using Backup Nodes.
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

Cut and Count and Representative Sets on Branch Decompositions.
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

A Faster Parameterized Algorithm for Pseudoforest Deletion.
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Subexponential Time Algorithms for Embedding H-Minor Free Graphs.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Exact algorithms for Kayles.
Theor. Comput. Sci., 2015

Google Scholar makes it hard - the complexity of organizing one's publications.
Inf. Process. Lett., 2015

Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality.
Electronic Notes in Discrete Mathematics, 2015

Speeding Up Dynamic Programming with Representative Sets: An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions.
Algorithmica, 2015

Erratum to: Editorial.
Algorithmica, 2015

Editorial.
Algorithmica, 2015

Definability Equals Recognizability for k-Outerplanar Graphs.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Practical Algorithms for Linear Boolean-width.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Subexponential Time Algorithms for Finding Small Tree and Path Decompositions.
Proceedings of the Algorithms - ESA 2015, 2015

PSPACE-Completeness of Bloxorz and of Games with 2-Buttons.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014
Kernelization Lower Bounds by Cross-Composition.
SIAM J. Discrete Math., 2014

Graph Modification Problems (Dagstuhl Seminar 14071).
Dagstuhl Reports, 2014

On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion.
Algorithmica, 2014

Lower Bounds for Kernelization.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Provisional Propagation for Verifying Monotonicity of Bayesian Networks.
Proceedings of the ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic, 2014

2013
Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter.
Theory Comput. Syst., 2013

Fixed-Parameter Tractability and Characterizations of Small Special Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

Speeding Up Dynamic Programming with Representative Sets - An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

The Fine Details of Fast Dynamic Programming over Tree Decompositions.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

An O(c^k n) 5-Approximation Algorithm for Treewidth.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
On switching classes, NLC-width, cliquewidth and treewidth.
Theor. Comput. Sci., 2012

Scheduling of pipelined operator graphs.
J. Scheduling, 2012

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs.
Theory Comput. Syst., 2012

Parameterized Complexity of the Spanning Tree Congestion Problem.
Algorithmica, 2012

Kernel Bounds for Structural Parameterizations of Pathwidth.
Proceedings of the Algorithm Theory - SWAT 2012, 2012

Fixed-Parameter Tractability of Treewidth and Pathwidth.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

2011
Treewidth computations II. Lower bounds.
Inf. Comput., 2011

Spanning tree congestion of k-outerplanar graphs.
Discrete Mathematics, 2011

Exact algorithms for dominating set.
Discrete Applied Mathematics, 2011

Exact Algorithms for Kayles.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

Exact Algorithms for Intervalizing Colored Graphs.
Proceedings of the Theory and Practice of Algorithms in (Computer) Systems, 2011

Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Cross-Composition: A New Technique for Kernelization Lower Bounds.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Partition into Triangles on Bounded Degree Graphs.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

A Local Search Algorithm for Branchwidth.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

Kernel Bounds for Path and Cycle Problems.
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

On Stopping Evidence Gathering for Diagnostic Bayesian Networks.
Proceedings of the Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2011

2010
A Cubic Kernel for Feedback Vertex Set and Loop Cutset.
Theory Comput. Syst., 2010

The Valve Location Problem in Simple Network Topologies.
INFORMS Journal on Computing, 2010

Treewidth computations I. Upper bounds.
Inf. Comput., 2010

Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions.
Algorithmica, 2010

Complexity Results for the Spanning Tree Congestion Problem.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

A Kernel for Convex Recoloring of Weighted Forests.
Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010

Faster Algorithms on Branch and Clique Decompositions.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

The Necessity of Bounded Treewidth for Efficient Inference in Bayesian Networks.
Proceedings of the ECAI 2010, 2010

2009
Derivation of algorithms for cutwidth and related graph layout parameters.
J. Comput. Syst. Sci., 2009

On problems without polynomial kernels.
J. Comput. Syst. Sci., 2009

Planar Capacitated Dominating Set Is W[1]-Hard.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Kernelization: New Upper and Lower Bound Techniques.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

(Meta) Kernelization.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution.
Proceedings of the Algorithms, 2009

Kernel Bounds for Disjoint Cycles and Disjoint Paths.
Proceedings of the Algorithms, 2009

2008
Treewidth of Graphs.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Combinatorial Optimization on Graphs of Bounded Treewidth.
Comput. J., 2008

The Valve Location Problem in Simple Network Topologies.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint.
Proceedings of the Algorithm Theory, 2008

Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set.
Proceedings of the STACS 2008, 2008

Clustering with Partial Information.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Exact Algorithms for Edge Domination.
Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

A Linear Kernel for Planar Feedback Vertex Set.
Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Faster Parameterized Algorithms for Minimum Fill-In.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

On Problems without Polynomial Kernels (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
Safe Reduction Rules for Weighted Treewidth.
Algorithmica, 2007

A Cubic Kernel for Feedback Vertex Set.
Proceedings of the STACS 2007, 2007

Treewidth: Structure and Algorithms.
Proceedings of the Structural Information and Communication Complexity, 2007

Weighted Treewidth Algorithmic Techniques and Results.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Wooden Geometric Puzzles: Design and Hardness Proofs.
Proceedings of the Fun with Algorithms, 4th International Conference, 2007

Local Monotonicity in Probabilistic Networks.
Proceedings of the Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2007

The valve location problem.
Proceedings of the Sixth Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2007

Quadratic Kernelization for Convex Recoloring of Trees.
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006
Contraction and Treewidth Lower Bounds.
J. Graph Algorithms Appl., 2006

Safe separators for treewidth.
Discrete Mathematics, 2006

Treewidth: Characterizations, Applications, and Computations.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

On Exact Algorithms for Treewidth.
Proceedings of the Algorithms, 2006

Kernelization for Convex Recoloring.
Proceedings of the Algorithms and Complexity in Durham 2006, 2006

A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth.
Proceedings of the Algorithmic Aspects in Information and Management, 2006

2005
On algorithms for (P5, gem)-free graphs.
Theor. Comput. Sci., 2005

Cutwidth II: Algorithms for partial w-trees of bounded degree.
J. Algorithms, 2005

Cutwidth I: A linear time fixed parameter algorithm.
J. Algorithms, 2005

Preprocessing Rules for Triangulation of Probabilistic Networks.
Computational Intelligence, 2005

Degree-Based Treewidth Lower Bounds.
Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

New Upper Bound Heuristics for Treewidth.
Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

Discovering Treewidth.
Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, 2005

Online topological ordering.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Algorithms for Graphs Embeddable with Few Crossings Per Edge.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions.
Proceedings of the Algorithms, 2005

Treewidth Lower Bounds with Brambles.
Proceedings of the Algorithms, 2005

2004
Radio Labeling with Preassigned Frequencies.
SIAM Journal on Optimization, 2004

Space-Efficient Construction Variants of Dynamic Programming.
Nord. J. Comput., 2004

A Note on Rectilinearity and Angular Resolution.
J. Graph Algorithms Appl., 2004

Approximations for lambda-Colorings of Graphs.
Comput. J., 2004

On the Maximum Cardinality Search Lower Bound for Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P4's.
Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

Monotonicity in Bayesian Networks.
Proceedings of the UAI '04, 2004

Equitable Colorings of Bounded Treewidth Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Computing Small Search Numbers in Linear Time.
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

Contraction and Treewidth Lower Bounds.
Proceedings of the Algorithms, 2004

Safe Seperators for Treewidth.
Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, 2004

2003
Necessary Edges in k-Chordalisations of Graphs.
J. Comb. Optim., 2003

Finding a bigtriangleup-regular supergraph of minimum order.
Discrete Applied Mathematics, 2003

Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Linear Time Algorithms for Some NP-Complete Problems on (P5, Gem)-Free Graphs.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002
Kayles and Nimbers.
J. Algorithms, 2002

Approximation of pathwidth of outerplanar graphs.
J. Algorithms, 2002

Sizes of Ordered Decision Trees.
Int. J. Found. Comput. Sci., 2002

Relaxed Update and Partition Network Games.
Fundam. Inform., 2002

Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs.
Algorithmica, 2002

Safe Reduction Rules for Weighted Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition.
Proceedings of the Algorithm Theory, 2002

Tree Decompositions with Small Cost.
Proceedings of the Algorithm Theory, 2002

Radio Labeling with Pre-assigned Frequencies.
Proceedings of the Algorithms, 2002

On the Complexity of the MPA Problem in Probabilistic Networks.
Proceedings of the 15th Eureopean Conference on Artificial Intelligence, 2002

2001
A Generic NP-hardness Proof for a Variant of Graph Coloring.
J. UCS, 2001

Reduction Algorithms for Graphs of Small Treewidth.
Inf. Comput., 2001

Treewidth: Computational Experiments.
Electronic Notes in Discrete Mathematics, 2001

Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two.
Algorithmica, 2001

Approximation of Pathwidth of Outerplanar Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

Pre-processing for Triangulation of Probabilistic Networks.
Proceedings of the UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, 2001

On Game-Theoretic Models of Networks.
Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth.
Proceedings of the Algorithms, 2001

2000
The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs.
Theor. Comput. Sci., 2000

Finding Small Equivalent Decision Trees is Hard.
Int. J. Found. Comput. Sci., 2000

The algorithmic theory of treewidth.
Electronic Notes in Discrete Mathematics, 2000

Introduction.
Algorithmica, 2000

Fixed Parameter Algorithms for PLANAR DOMINATING SET and Related Problems.
Proceedings of the Algorithm Theory, 2000

lambda-Coloring of Graphs.
Proceedings of the STACS 2000, 2000

Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width.
Proceedings of the Algorithms and Computation, 11th International Conference, 2000

1999
Graphs with Branchwidth at Most Three.
J. Algorithms, 1999

SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s.
Electronic Notes in Discrete Mathematics, 1999

A note on domino treewidth.
Discrete Mathematics & Theoretical Computer Science, 1999

Graph Automorphisms with Maximal Projection Distances.
Proceedings of the Fundamentals of Computation Theory, 12th International Symposium, 1999

Finding a minimal tree in a polygon with its medial axis.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

1998
A Partial k-Arboretum of Graphs with Bounded Treewidth.
Theor. Comput. Sci., 1998

Rankings of Graphs.
SIAM J. Discrete Math., 1998

Treewidth and Minimum Fill-in on d-Trapezoid Graphs.
J. Graph Algorithms Appl., 1998

Linear-Time Register Allocation for a Fixed Number of Registers.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Tree Decompositions of Small Diameter.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997
Domino Treewidth.
J. Algorithms, 1997

Fast Partitioning l-Apex Graphs with Application to Approximating Maximum Induced-Subgraph Problems.
Inf. Process. Lett., 1997

It is Hard to Know when Greedy is Good for Finding Independent Sets.
Inf. Process. Lett., 1997

On Interval Routing Schemes and Treewidth.
Inf. Comput., 1997

Treewidth for Graphs with Small Chordality.
Discrete Applied Mathematics, 1997

Parallel Algorithms for Treewidth Two.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

Treewidth: Algorithmoc Techniques and Results.
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Constructive Linear Time Algorithms for Branchwidth.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Isomorphism for Graphs of Bounded Distance Width.
Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997

1996
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs.
J. Algorithms, 1996

On Intervalizing K-colored Graphs for DNA Physical Mapping.
Discrete Applied Mathematics, 1996

Parallel Algorithms for Series Parallel Graphs.
Proceedings of the Algorithms, 1996

Finite-State Computability of Annotations of Strings and Trees.
Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

Reduction Algorithms for Constructing Solutions in Graphs with Small Treewidth.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995
Restrictions of Graph Partition Problems. Part I.
Theor. Comput. Sci., 1995

W[2]-hardness of precedence constrained K-processor scheduling.
Oper. Res. Lett., 1995

Complexity Aspects of Two-Dimensional Data Compression.
Nord. J. Comput., 1995

Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree.
J. Algorithms, 1995

Parameterized complexity analysis in computational biology.
Computer Applications in the Biosciences, 1995

On Interval Routing Schemes and Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995

Parallel Algorithms with Optimal Speedup for Bounded Treewidth.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Intervalizing k-Colored Graphs.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994
The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case
Inf. Comput., January, 1994

Trade-Offs in Non-Reversing Diameter.
Nord. J. Comput., 1994

Domino Treewith (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

Ranking of Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On the Complexity of the Maximum Cut Problem.
Proceedings of the STACS 94, 1994

Erratum: Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators.
Proceedings of the Algorithms, 1994

The Parameterized Complexity of Sequence Alignment and Consensus.
Proceedings of the Combinatorial Pattern Matching, 5th Annual Symposium, 1994

1993
Complexity of Path-Forming Games.
Theor. Comput. Sci., 1993

Book review.
ZOR - Meth. & Mod. of OR, 1993

On Linear Time Minor Tests with Depth-First Search.
J. Algorithms, 1993

A Tourist Guide through Treewidth.
Acta Cybern., 1993

Dynamic Algorithms for Graphs with Treewidth 2.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1993

On Reduction Algorithms for Graphs with Small Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1993

A linear time algorithm for finding tree-decompositions of small treewidth.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On the Complexity of Scheduling Incompatible Jobs with Unit-Times.
Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

Treewidth and Pathwidth of Permutation Graphs.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators.
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

1992
Scheduling with Incompatible Jobs
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992

The Complexity of Coloring Games on Perfect Graphs.
Theor. Comput. Sci., 1992

Scheduling with Incompatible Jobs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

Kayles on Special Classes of Graphs - An Application of Sprague-Grundy Theory.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

Testing Superperfection of k-Trees.
Proceedings of the Algorithm Theory, 1992

Triangulating Planar Graphs While Minimizing the Maximum Degree.
Proceedings of the Algorithm Theory, 1992

A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs.
Proceedings of the STACS 92, 1992

Approximating Treewidth and Pathwidth of some Classes of Perfect Graphs.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

Two Strikes Against Perfect Phylogeny.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991
New Lower Bound Techniques for Distributed Leader Finding and Other Problems on Rings of Processors.
Theor. Comput. Sci., 1991

Some Lower Bound Results for Decentralized Extrema-Finding in Rings of Processors.
J. Comput. Syst. Sci., 1991

Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height.
Proceedings of the 17th International Workshop, 1991

On Disjoint Cycles.
Proceedings of the 17th International Workshop, 1991

Planar Graph Augmentation Problems (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 1991

Better Algorithms for the Pathwidth and Treewidth of Graphs.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Complexity Aspects of Map Compression.
Proceedings of the IEEE Data Compression Conference, 1991

1990
The Complexity of Finding Uniform Emulations on Paths and Ring Networks
Inf. Comput., May, 1990

Bit-Optimal Election in Synchronous Rings.
Inf. Process. Lett., 1990

Computational complexity of norm-maximization.
Combinatorica, 1990

On the Complexity of Some Coloring Games.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1990

The Pathwidth and Treewidth of Cographs.
Proceedings of the SWAT 90, 1990

1989
The Classification of Coverings of Processor Networks.
J. Parallel Distrib. Comput., 1989

Achromatic Number is NP-Complete for Cographs and Interval Graphs.
Inf. Process. Lett., 1989

Improved Self-Reduction Algorithms for Graphs with Bounded Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1989

On Linear Time Minor Tests and Depth First Search.
Proceedings of the Algorithms and Data Structures, 1989

Distributed Computing on TRansitive Networks: The Thorus.
Proceedings of the STACS 89, 1989

The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case.
Proceedings of the Fundamentals of Computation Theory, 1989

1988
The Complexity of Finding Uniform Emulations on Fixed Graphs.
Inf. Process. Lett., 1988

A Better Lower Bound For Distributed Leader Finding in Bidirectional, Asynchronous Rings of Processors.
Inf. Process. Lett., 1988

Some Classes of Graphs with Bounded Treewidth.
Bulletin of the EATCS, 1988

NC-Algorithms for Graphs with Small Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1988

Polynomial Algorithms for Graph Isomorphism and Chromatic Index on Partial k-Trees.
Proceedings of the SWAT 88, 1988

Dynamic Programming on Graphs with Bounded Treewidth.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

1987
Diameter increase caused by edge deletion.
Journal of Graph Theory, 1987

New Lower Bounds for Distributed Leader Finding in Asynchronous Rings of Processors.
Proceedings of the GI, 1987

1986
Simulation of Large Networks on Smaller Networks
Information and Control, December, 1986

Improved Diameter Bounds for Altered Graphs.
Proceedings of the Graphtheoretic Concepts in Computer Science, International Workshop, 1986

New Upperbounds for Decentralized Extrema-Finding in a Ring of Processors.
Proceedings of the STACS 86, 1986

1985
Simulation of Large Networks on Smaller Networks.
Proceedings of the STACS 85, 1985


  Loading...