Hans L. Bodlaender

Orcid: 0000-0002-9297-3330

Affiliations:
  • Utrecht University, Netherlands


According to our database1, Hans L. Bodlaender authored at least 278 papers between 1986 and 2024.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Parameterized problems complete for nondeterministic FPT time and logarithmic space.
Inf. Comput., 2024

XNLP-hardness of Parameterized Problems on Planar Graphs.
CoRR, 2024

Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem.
Proceedings of the Combinatorial Algorithms - 35th International Workshop, 2024

2023
An ETH-Tight Exact Algorithm for Euclidean TSP.
SIAM J. Comput., June, 2023

Efficiently computing the Shapley value of connectivity games in low-treewidth graphs.
Oper. Res., March, 2023

Typical Sequences Revisited - Computing Width Parameters of Graphs.
Theory Comput. Syst., February, 2023

Treewidth is NP-Complete on Cubic Graphs (and related results).
CoRR, 2023

The Parameterised Complexity Of Integer Multicommodity Flow.
Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Treewidth Is NP-Complete on Cubic Graphs.
Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022
Constructing tree decompositions of graphs with bounded gonality.
J. Comb. Optim., 2022

Dynamic sampling from a discrete probability distribution with a known distribution of rates.
Comput. Stat., 2022

The Parameterized Complexity Binary CSP for Graphs with a Small Vertex Cover and Related Results.
CoRR, 2022

Parameterized Complexity Results for Bayesian Inference.
CoRR, 2022

XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure.
CoRR, 2022

Problems Hard for Treewidth but Easy for Stable Gonality.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

From the W-hierarchy to XNLP - Classes of Fixed Parameter Intractability.
Proceedings of the WALCOM: Algorithms and Computation, 2022

Parameterized Completeness Results for Bayesian Inference.
Proceedings of the International Conference on Probabilistic Graphical Models, 2022

On the Complexity of Problems on Tree-Structured Graphs.
Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure.
Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

On the Parameterized Complexity of Computing Tree-Partitions.
Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

List Colouring Trees in Logarithmic Space.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021
Steiner trees for hereditary graph classes: A treewidth perspective.
Theor. Comput. Sci., 2021

Parameterized Complexity of Conflict-Free Graph Coloring.
SIAM J. Discret. Math., 2021

Stable Divisorial Gonality is in NP.
Theory Comput. Syst., 2021

Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2021

Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes.
Proceedings of the WALCOM: Algorithms and Computation, 2021

Parameterized Complexities of Dominating and Independent Set Reconfiguration.
Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

2020
On the exact complexity of polyomino packing.
Theor. Comput. Sci., 2020

Recognizing hyperelliptic graphs in polynomial time.
Theor. Comput. Sci., 2020

A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs.
SIAM J. Comput., 2020

EATCS-IPEC Nerode Prize 2020 - Call for Nominations.
Bull. EATCS, 2020

Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection Graph Classes.
CoRR, 2020

Subgraph Isomorphism on Graph Classes that Exclude a Substructure.
Algorithmica, 2020

Knot Diagrams of Treewidth Two.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Steiner Trees for Hereditary Graph Classes.
Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Parameterized Complexity of Scheduling Chains of Jobs with Delays.
Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Hedonic Seat Arrangement Problems.
Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, 2020

2019
On the maximum weight minimal separator.
Theor. Comput. Sci., 2019

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

EATCS-IPEC Nerode Prize 2019 - Call for Nominations.
Bull. EATCS, 2019

Typical Sequences Revisited - Algorithms for Linear Orderings of Series Parallel Digraphs.
CoRR, 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

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

2018
A faster parameterized algorithm for Pseudoforest Deletion.
Discret. Appl. Math., 2018

On Exploring Temporal Graphs of Small Pathwidth.
CoRR, 2018

Fast Dynamic Programming on Graph Decompositions.
CoRR, 2018

Optimal data structures for stochastic driven simulations.
CoRR, 2018

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity.
Algorithmica, 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

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.
Discret. Appl. Math., 2017

The Homogeneous Broadcast Problem in Narrow and Wide Strips.
Proceedings of the Algorithms and Data Structures - 15th International Symposium, 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 c<sup>k</sup> n 5-Approximation Algorithm for Treewidth.
SIAM J. Comput., 2016

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

(Meta) Kernelization.
J. ACM, 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

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

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.
Inf. Comput., 2015

Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality.
Electron. Notes Discret. Math., 2015

MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree k-Outerplanar Graphs.
CoRR, 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. Discret. 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
Kernel bounds for path and cycle problems.
Theor. Comput. Sci., 2013

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.
SIAM J. Discret. Math., 2013

Partition Into Triangles on Bounded Degree Graphs.
Theory Comput. Syst., 2013

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

A O(c^k n) 5-Approximation Algorithm for Treewidth
CoRR, 2013

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

The Fine Details of Fast Dynamic Programming over Tree Decompositions.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 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

On exact algorithms for treewidth.
ACM Trans. Algorithms, 2012

Scheduling of pipelined operator graphs.
J. Sched., 2012

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

Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
CoRR, 2012

Exact Algorithms for Edge Domination.
Algorithmica, 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
Kernel bounds for disjoint cycles and disjoint paths.
Theor. Comput. Sci., 2011

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

Spanning tree congestion of k-outerplanar graphs.
Discret. Math., 2011

Exact algorithms for dominating set.
Discret. Appl. Math., 2011

Faster Parameterized Algorithms for Minimum Fill-in.
Algorithmica, 2011

Quadratic Kernelization for Convex Recoloring of Trees.
Algorithmica, 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

Cross-Composition: A New Technique for Kernelization Lower Bounds.
Proceedings of the 28th International Symposium on Theoretical Aspects 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 <i>k</i>th Most Probable Explanations in Probabilistic Networks.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

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

2010
Clustering with partial information.
Theor. Comput. Sci., 2010

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

The Valve Location Problem in Simple Network Topologies.
INFORMS J. Comput., 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
Wooden Geometric Puzzles: Design and Hardness Proofs.
Theory Comput. Syst., 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

On the minimum corridor connection problem and other generalized geometric problems.
Comput. Geom., 2009

Planar Capacitated Dominating Set Is <i>W</i>[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

Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution.
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

Treewidth Lower Bounds with Brambles.
Algorithmica, 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

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

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

2007
On the maximum cardinality search lower bound for treewidth.
Discret. Appl. Math., 2007

Algorithms for Graphs Embeddable with Few Crossings per Edge.
Algorithmica, 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

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

2006
Online topological ordering.
ACM Trans. Algorithms, 2006

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

Safe separators for treewidth.
Discret. Math., 2006

Treewidth: Characterizations, Applications, and Computations.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 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
Equitable colorings of bounded treewidth graphs.
Theor. Comput. Sci., 2005

On algorithms for (<i>P</i><sub>5</sub>, 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

Tree decompositions with small cost.
Discret. Appl. Math., 2005

Preprocessing Rules for Triangulation of Probabilistic Networks.
Comput. Intell., 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

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

2004
Radio Labeling with Preassigned Frequencies.
SIAM J. Optim., 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

Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P<sub>4</sub>'s.
Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

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

Computing Small Search Numbers in Linear Time.
Proceedings of the Parameterized and Exact Computation, First International Workshop, 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.
Discret. Appl. Math., 2003

Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition.
Algorithmica, 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 (P<sub>5</sub>, 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. Informaticae, 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

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 European Conference on Artificial Intelligence, 2002

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

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

Treewidth: Computational Experiments.
Electron. Notes Discret. Math., 2001

Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two.
Algorithmica, 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

On the Complexity of the Maximum Cut Problem.
Nord. J. Comput., 2000

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

The algorithmic theory of treewidth.
Electron. Notes Discret. Math., 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 P<sub>4</sub>s.
Electron. Notes Discret. Math., 1999

A note on domino treewidth.
Discret. Math. Theor. Comput. Sci., 1999

Isomorphism for Graphs of Bounded Distance Width.
Algorithmica, 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 <i>k</i>-Arboretum of Graphs with Bounded Treewidth.
Theor. Comput. Sci., 1998

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

Parallel Algorithms with Optimal Speedup for Bounded Treewidth.
SIAM J. Comput., 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

Triangulating Planar Graphs while Minimizing the Maximum Degree.
Inf. Comput., 1997

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

Treewidth for Graphs with Small Chordality.
Discret. Appl. Math., 1997

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

Treewidth: Algorithmic 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

1996
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth.
SIAM J. Comput., 1996

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

On Intervalizing K-colored Graphs for DNA Physical Mapping.
Discret. Appl. Math., 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

The Parameterized Complexity of Sequence Alignment and Consensus.
Theor. Comput. Sci., 1995

Treewidth and Pathwidth of Permutation Graphs.
SIAM J. Discret. Math., 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.
Comput. Appl. Biosci., 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

On Disjoint Cycles.
Int. J. Found. Comput. Sci., 1994

Scheduling with Incompatible Jobs.
Discret. Appl. Math., 1994

Improved Self-reduction Algorithms for Graphs with Bounded Treewidth.
Discret. Appl. Math., 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

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

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

The Pathwidth and Treewidth of Cographs.
SIAM J. Discret. Math., 1993

Book review.
ZOR Methods Model. Oper. Res., 1993

A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs.
J. Algorithms, 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

On the Complexity of Scheduling Incompatible Jobs with Unit-Times.
Proceedings of the Mathematical Foundations of Computer Science 1993, 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
The Complexity of Coloring Games on Perfect Graphs.
Theor. Comput. Sci., 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

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

On the Complexity of Some Coloring Games.
Int. J. Found. Comput. Sci., 1991

Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height.
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

Polynomial Algorithms for Graph Isomorphism and Chromatic Index on Partial k-Trees.
J. Algorithms, 1990

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

Computational complexity of norm-maximization.
Comb., 1990

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

Achromatic Number is NP-Complete for Cographs and Interval Graphs.
Inf. Process. Lett., 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

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.
Bull. EATCS, 1988

NC-Algorithms for Graphs with Small Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 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.
J. 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
Inf. 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


  Loading...