Hans L. Bodlaender

Céline M. F. Swennenhuis

Inf. Comput., 2024

XNLP-hardness of Parameterized Problems on Planar Graphs.

[BibT_eX]

[DOI]

Krisztina Szilágyi

CoRR, 2024

Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 35th International Workshop, 2024

2023

An ETH-Tight Exact Algorithm for Euclidean TSP.

[BibT_eX]

[DOI]

SIAM J. Comput., June, 2023

Efficiently computing the Shapley value of connectivity games in low-treewidth graphs.

[BibT_eX]

[DOI]

Herbert J. M. Hamers

Oper. Res., March, 2023

Typical Sequences Revisited - Computing Width Parameters of Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., February, 2023

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

[BibT_eX]

[DOI]

CoRR, 2023

The Parameterised Complexity Of Integer Multicommodity Flow.

[BibT_eX]

[DOI]

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Treewidth Is NP-Complete on Cubic Graphs.

[BibT_eX]

[DOI]

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters.

[BibT_eX]

[DOI]

Michal Pilipczuk

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Constructing tree decompositions of graphs with bounded gonality.

[BibT_eX]

[DOI]

Josse van Dobben de Bruyn

Dion Gijswijt

Harry Smit

J. Comb. Optim., 2022

Dynamic sampling from a discrete probability distribution with a known distribution of rates.

[BibT_eX]

[DOI]

Federico D'Ambrosio

Gerard T. Barkema

Comput. Stat., 2022

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

[BibT_eX]

[DOI]

CoRR, 2022

Parameterized Complexity Results for Bayesian Inference.

[BibT_eX]

[DOI]

Nils Donselaar

CoRR, 2022

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

[BibT_eX]

[DOI]

Hugo Jacob

CoRR, 2022

Problems Hard for Treewidth but Easy for Stable Gonality.

[BibT_eX]

[DOI]

Gunther Cornelissen

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

From the W-hierarchy to XNLP - Classes of Fixed Parameter Intractability.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation, 2022

Parameterized Completeness Results for Bayesian Inference.

[BibT_eX]

[DOI]

Nils Donselaar

Proceedings of the International Conference on Probabilistic Graphical Models, 2022

On the Complexity of Problems on Tree-Structured Graphs.

[BibT_eX]

[DOI]

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure.

[BibT_eX]

[DOI]

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

On the Parameterized Complexity of Computing Tree-Partitions.

[BibT_eX]

[DOI]

Hugo Jacob

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

List Colouring Trees in Logarithmic Space.

[BibT_eX]

[DOI]

Hugo Jacob

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Steiner trees for hereditary graph classes: A treewidth perspective.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Parameterized Complexity of Conflict-Free Graph Coloring.

[BibT_eX]

[DOI]

Sudeshna Kolay

Astrid Pieterse

SIAM J. Discret. Math., 2021

Stable Divisorial Gonality is in NP.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2021

Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation.

[BibT_eX]

[DOI]

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

Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes.

[BibT_eX]

[DOI]

Toshiki Saitoh

Ryo Yoshinaka

Proceedings of the WALCOM: Algorithms and Computation, 2021

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

[BibT_eX]

[DOI]

Céline M. F. Swennenhuis

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

2020

On the exact complexity of polyomino packing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Recognizing hyperelliptic graphs in polynomial time.

[BibT_eX]

[DOI]

Jelco M. Bodewes

Gunther Cornelissen

Theor. Comput. Sci., 2020

A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

EATCS-IPEC Nerode Prize 2020 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2020

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

[BibT_eX]

[DOI]

Toshiki Saitoh

Ryo Yoshinaka

CoRR, 2020

Subgraph Isomorphism on Graph Classes that Exclude a Substructure.

[BibT_eX]

[DOI]

Algorithmica, 2020

Knot Diagrams of Treewidth Two.

[BibT_eX]

[DOI]

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

Steiner Trees for Hereditary Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Parameterized Complexity of Scheduling Chains of Jobs with Delays.

[BibT_eX]

[DOI]

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Hedonic Seat Arrangement Problems.

[BibT_eX]

[DOI]

Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, 2020

2019

On the maximum weight minimal separator.

[BibT_eX]

[DOI]

Tesshu Hanaka

Hirotaka Ono

Theor. Comput. Sci., 2019

On exploring always-connected temporal graphs of small pathwidth.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2019

EATCS-IPEC Nerode Prize 2019 - Call for Nominations.

[BibT_eX]

[DOI]

Jianer Chen

Virginia Vassilevska Williams

Bull. EATCS, 2019

Typical Sequences Revisited - Algorithms for Linear Orderings of Series Parallel Digraphs.

[BibT_eX]

[DOI]

CoRR, 2019

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

[BibT_eX]

[DOI]

Mark de Berg

Sándor Kisfaludi-Bak

Algorithmica, 2019

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

[BibT_eX]

[DOI]

Mark de Berg

Sándor Kisfaludi-Bak

Algorithmica, 2019

Subgraph Isomorphism on Graph Classes that Exclude a Substructure.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2018

A faster parameterized algorithm for Pseudoforest Deletion.

[BibT_eX]

[DOI]

Hirotaka Ono

Yota Otachi

Discret. Appl. Math., 2018

On Exploring Temporal Graphs of Small Pathwidth.

[BibT_eX]

[DOI]

CoRR, 2018

Fast Dynamic Programming on Graph Decompositions.

[BibT_eX]

[DOI]

CoRR, 2018

Optimal data structures for stochastic driven simulations.

[BibT_eX]

[DOI]

Federico D'Ambrosio

Gerard T. Barkema

CoRR, 2018

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity.

[BibT_eX]

[DOI]

Hirotaka Ono

Yota Otachi

Algorithmica, 2018

A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Eur. J. Comb., 2017

Characterizing width two for variants of treewidth.

[BibT_eX]

[DOI]

Vincent J. C. Kreuzen

O-joung Kwon

Seongmin Ok

Discret. Appl. Math., 2017

The Homogeneous Broadcast Problem in Narrow and Wide Strips.

[BibT_eX]

[DOI]

Mark de Berg

Sándor Kisfaludi-Bak

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Computing Treewidth on the GPU.

[BibT_eX]

[DOI]

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Improved Lower Bounds for Graph Embedding Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016

Treewidth of Graphs.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Kernelization, Exponential Lower Bounds.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

A ck n 5-Approximation Algorithm for Treewidth.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Exact Algorithms for Intervalizing Coloured Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

(Meta) Kernelization.

[BibT_eX]

[DOI]

J. ACM, 2016

Robust Recoverable Path Using Backup Nodes.

[BibT_eX]

[DOI]

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

Cut and Count and Representative Sets on Branch Decompositions.

[BibT_eX]

[DOI]

Willem J. A. Pino

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Subexponential Time Algorithms for Embedding H-Minor Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Exact algorithms for Kayles.

[BibT_eX]

[DOI]

Sjoerd T. Timmer

Theor. Comput. Sci., 2015

Google Scholar makes it hard - the complexity of organizing one's publications.

[BibT_eX]

[DOI]

Marc J. van Kreveld

Inf. Process. Lett., 2015

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.

[BibT_eX]

[DOI]

Inf. Comput., 2015

Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality.

[BibT_eX]

[DOI]

Pinar Heggernes

Electron. Notes Discret. Math., 2015

MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree k-Outerplanar Graphs.

[BibT_eX]

[DOI]

CoRR, 2015

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

[BibT_eX]

[DOI]

Stefan Fafianie

Algorithmica, 2015

Erratum to: Editorial.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Giuseppe F. Italiano

Algorithmica, 2015

Editorial.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Giuseppe F. Italiano

Algorithmica, 2015

Definability Equals Recognizability for k-Outerplanar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Practical Algorithms for Linear Boolean-width.

[BibT_eX]

[DOI]

Chiel B. Ten Brinke

Frank J. P. van Houten

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Subexponential Time Algorithms for Finding Small Tree and Path Decompositions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

PSPACE-Completeness of Bloxorz and of Games with 2-Buttons.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014

Kernelization Lower Bounds by Cross-Composition.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Graph Modification Problems (Dagstuhl Seminar 14071).

[BibT_eX]

[DOI]

Pinar Heggernes

Daniel Lokshtanov

Dagstuhl Reports, 2014

On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion.

[BibT_eX]

[DOI]

Algorithmica, 2014

Lower Bounds for Kernelization.

[BibT_eX]

[DOI]

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

Provisional Propagation for Verifying Monotonicity of Bayesian Networks.

[BibT_eX]

[DOI]

Merel T. Rietbergen

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Partition Into Triangles on Bounded Degree Graphs.

[BibT_eX]

[DOI]

Marcel E. van Kooten Niekerk

Theory Comput. Syst., 2013

Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2013

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

[BibT_eX]

[DOI]

CoRR, 2013

Fixed-Parameter Tractability and Characterizations of Small Special Treewidth.

[BibT_eX]

[DOI]

Vincent J. C. Kreuzen

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

The Fine Details of Fast Dynamic Programming over Tree Decompositions.

[BibT_eX]

[DOI]

Paul S. Bonsma

Daniel Lokshtanov

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

An O(c^k n) 5-Approximation Algorithm for Treewidth.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

On switching classes, NLC-width, cliquewidth and treewidth.

[BibT_eX]

[DOI]

Jurriaan Hage

Theor. Comput. Sci., 2012

On exact algorithms for treewidth.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Scheduling of pipelined operator graphs.

[BibT_eX]

[DOI]

Petra Schuurman

Gerhard J. Woeginger

J. Sched., 2012

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2012

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

[BibT_eX]

[DOI]

CoRR, 2012

Exact Algorithms for Edge Domination.

[BibT_eX]

[DOI]

Algorithmica, 2012

Parameterized Complexity of the Spanning Tree Congestion Problem.

[BibT_eX]

[DOI]

Algorithmica, 2012

Kernel Bounds for Structural Parameterizations of Pathwidth.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Fixed-Parameter Tractability of Treewidth and Pathwidth.

[BibT_eX]

[DOI]

Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

2011

Kernel bounds for disjoint cycles and disjoint paths.

[BibT_eX]

[DOI]

Stéphan Thomassé

Anders Yeo

Theor. Comput. Sci., 2011

Treewidth computations II. Lower bounds.

[BibT_eX]

[DOI]

Inf. Comput., 2011

Spanning tree congestion of k-outerplanar graphs.

[BibT_eX]

[DOI]

Discret. Math., 2011

Exact algorithms for dominating set.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

Faster Parameterized Algorithms for Minimum Fill-in.

[BibT_eX]

[DOI]

Pinar Heggernes

Yngve Villanger

Algorithmica, 2011

Quadratic Kernelization for Convex Recoloring of Trees.

[BibT_eX]

[DOI]

Algorithmica, 2011

Exact Algorithms for Kayles.

[BibT_eX]

[DOI]

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

Exact Algorithms for Intervalizing Colored Graphs.

[BibT_eX]

[DOI]

Proceedings of the Theory and Practice of Algorithms in (Computer) Systems, 2011

Cross-Composition: A New Technique for Kernelization Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

A Local Search Algorithm for Branchwidth.

[BibT_eX]

[DOI]

Arnold Overwijk

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

The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks.

[BibT_eX]

[DOI]

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

On Stopping Evidence Gathering for Diagnostic Bayesian Networks.

[BibT_eX]

[DOI]

Proceedings of the Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2011

2010

Clustering with partial information.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

A Cubic Kernel for Feedback Vertex Set and Loop Cutset.

[BibT_eX]

[DOI]

Thomas C. van Dijk

Theory Comput. Syst., 2010

The Valve Location Problem in Simple Network Topologies.

[BibT_eX]

[DOI]

Albert Hendriks

Nadejda V. Grigorieva

INFORMS J. Comput., 2010

Treewidth computations I. Upper bounds.

[BibT_eX]

[DOI]

Inf. Comput., 2010

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

[BibT_eX]

[DOI]

Algorithmica, 2010

Complexity Results for the Spanning Tree Congestion Problem.

[BibT_eX]

[DOI]

Yota Otachi

Erik Jan van Leeuwen

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

A Kernel for Convex Recoloring of Weighted Forests.

[BibT_eX]

[DOI]

Marc Comas

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

Faster Algorithms on Branch and Clique Decompositions.

[BibT_eX]

[DOI]

Erik Jan van Leeuwen

Martin Vatshelle

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

The Necessity of Bounded Treewidth for Efficient Inference in Bayesian Networks.

[BibT_eX]

[DOI]

Proceedings of the ECAI 2010, 2010

2009

Wooden Geometric Puzzles: Design and Hardness Proofs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2009

Derivation of algorithms for cutwidth and related graph layout parameters.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2009

On problems without polynomial kernels.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2009

On the minimum corridor connection problem and other generalized geometric problems.

[BibT_eX]

[DOI]

Comput. Geom., 2009

Planar Capacitated Dominating Set Is W[1]-Hard.

[BibT_eX]

[DOI]

Daniel Lokshtanov

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Kernelization: New Upper and Lower Bound Techniques.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution.

[BibT_eX]

[DOI]

Peter Rossmanith

Proceedings of the Algorithms, 2009

2008

Treewidth of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Combinatorial Optimization on Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

Comput. J., 2008

Treewidth Lower Bounds with Brambles.

[BibT_eX]

[DOI]

Algorithmica, 2008

Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2008

Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

A Linear Kernel for Planar Feedback Vertex Set.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs.

[BibT_eX]

[DOI]

Richard B. Tan

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

On Problems without Polynomial Kernels (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

On the maximum cardinality search lower bound for treewidth.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

Algorithms for Graphs Embeddable with Few Crossings per Edge.

[BibT_eX]

[DOI]

Algorithmica, 2007

Safe Reduction Rules for Weighted Treewidth.

[BibT_eX]

[DOI]

Algorithmica, 2007

A Cubic Kernel for Feedback Vertex Set.

[BibT_eX]

[DOI]

Proceedings of the STACS 2007, 2007

Treewidth: Structure and Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2007

Weighted Treewidth Algorithmic Techniques and Results.

[BibT_eX]

[DOI]

Emgad H. Bachoore

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Local Monotonicity in Probabilistic Networks.

[BibT_eX]

[DOI]

Proceedings of the Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2007

The valve location problem.

[BibT_eX]

Nadejda V. Grigorieva

Albert Hendriks

Proceedings of the Sixth Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2007

2006

Online topological ordering.

[BibT_eX]

[DOI]

Irit Katriel

ACM Trans. Algorithms, 2006

Contraction and Treewidth Lower Bounds.

[BibT_eX]

[DOI]

Thomas Wolle

J. Graph Algorithms Appl., 2006

Safe separators for treewidth.

[BibT_eX]

[DOI]

Discret. Math., 2006

Treewidth: Characterizations, Applications, and Computations.

[BibT_eX]

[DOI]

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

Kernelization for Convex Recoloring.

[BibT_eX]

Proceedings of the Algorithms and Complexity in Durham 2006, 2006

A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth.

[BibT_eX]

[DOI]

Emgad H. Bachoore

Proceedings of the Algorithmic Aspects in Information and Management, 2006

2005

Equitable colorings of bounded treewidth graphs.

[BibT_eX]

[DOI]

Fedor V. Fomin

Theor. Comput. Sci., 2005

On algorithms for (P5, gem)-free graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

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

[BibT_eX]

[DOI]

J. Algorithms, 2005

Cutwidth I: A linear time fixed parameter algorithm.

[BibT_eX]

[DOI]

J. Algorithms, 2005

Tree decompositions with small cost.

[BibT_eX]

[DOI]

Fedor V. Fomin

Discret. Appl. Math., 2005

Preprocessing Rules for Triangulation of Probabilistic Networks.

[BibT_eX]

[DOI]

Comput. Intell., 2005

Degree-Based Treewidth Lower Bounds.

[BibT_eX]

[DOI]

Thomas Wolle

Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

New Upper Bound Heuristics for Treewidth.

[BibT_eX]

[DOI]

Emgad H. Bachoore

Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

Discovering Treewidth.

[BibT_eX]

[DOI]

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

Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

2004

Radio Labeling with Preassigned Frequencies.

[BibT_eX]

[DOI]

SIAM J. Optim., 2004

Space-Efficient Construction Variants of Dynamic Programming.

[BibT_eX]

Nord. J. Comput., 2004

A Note on Rectilinearity and Angular Resolution.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2004

Approximations for lambda-Colorings of Graphs.

[BibT_eX]

[DOI]

Comput. J., 2004

Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P4's.

[BibT_eX]

[DOI]

Celina M. H. de Figueiredo

Marisa Gutierrez

Rolf Niedermeier

Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

Monotonicity in Bayesian Networks.

[BibT_eX]

[DOI]

A. J. Feelders

Proceedings of the UAI '04, 2004

Computing Small Search Numbers in Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

Safe Seperators for Treewidth.

[BibT_eX]

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.

[BibT_eX]

[DOI]

J. Comb. Optim., 2003

Finding a bigtriangleup-regular supergraph of minimum order.

[BibT_eX]

[DOI]

Richard B. Tan

Discret. Appl. Math., 2003

Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition.

[BibT_eX]

[DOI]

Udi Rotics

Algorithmica, 2003

Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Linear Time Algorithms for Some NP-Complete Problems on (P5, Gem)-Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002

Kayles and Nimbers.

[BibT_eX]

[DOI]

J. Algorithms, 2002

Approximation of pathwidth of outerplanar graphs.

[BibT_eX]

[DOI]

Fedor V. Fomin

J. Algorithms, 2002

Sizes of Ordered Decision Trees.

[BibT_eX]

[DOI]

Hans Zantema

Int. J. Found. Comput. Sci., 2002

Relaxed Update and Partition Network Games.

[BibT_eX]

[DOI]

Michael J. Dinneen

Bakhadyr Khoussainov

Fundam. Informaticae, 2002

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

[BibT_eX]

[DOI]

Algorithmica, 2002

Safe Reduction Rules for Weighted Treewidth.

[BibT_eX]

[DOI]

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

Radio Labeling with Pre-assigned Frequencies.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2002

On the Complexity of the MPA Problem in Probabilistic Networks.

[BibT_eX]

Proceedings of the 15th European Conference on Artificial Intelligence, 2002

2001

A Generic NP-hardness Proof for a Variant of Graph Coloring.

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 2001

Reduction Algorithms for Graphs of Small Treewidth.

[BibT_eX]

[DOI]

Babette van Antwerpen-de Fluiter

Inf. Comput., 2001

Treewidth: Computational Experiments.

[BibT_eX]

[DOI]

Stan P. M. van Hoesel

Electron. Notes Discret. Math., 2001

Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two.

[BibT_eX]

[DOI]

Babette van Antwerpen-de Fluiter

Algorithmica, 2001

Pre-processing for Triangulation of Probabilistic Networks.

[BibT_eX]

[DOI]

Proceedings of the UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, 2001

On Game-Theoretic Models of Networks.

[BibT_eX]

[DOI]

Michael J. Dinneen

Bakhadyr Khoussainov

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

A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2001

2000

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

On the Complexity of the Maximum Cut Problem.

[BibT_eX]

Nord. J. Comput., 2000

Finding Small Equivalent Decision Trees is Hard.

[BibT_eX]

[DOI]

Hans Zantema

Int. J. Found. Comput. Sci., 2000

The algorithmic theory of treewidth.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2000

Introduction.

[BibT_eX]

[DOI]

Algorithmica, 2000

Fixed Parameter Algorithms for PLANAR DOMINATING SET and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2000

lambda-Coloring of Graphs.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 11th International Conference, 2000

1999

Graphs with Branchwidth at Most Three.

[BibT_eX]

[DOI]

J. Algorithms, 1999

SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s.

[BibT_eX]

[DOI]

Rolf Niedermeier

Electron. Notes Discret. Math., 1999

A note on domino treewidth.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 1999

Isomorphism for Graphs of Bounded Distance Width.

[BibT_eX]

[DOI]

Koichi Yamazaki

Algorithmica, 1999

Graph Automorphisms with Maximal Projection Distances.

[BibT_eX]

[DOI]

H. N. de Ridder

Proceedings of the Fundamentals of Computation Theory, 12th International Symposium, 1999

Finding a minimal tree in a polygon with its medial axis.

[BibT_eX]

[DOI]

Herman J. Haverkort

Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

1998

A Partial k-Arboretum of Graphs with Bounded Treewidth.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Rankings of Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1998

Parallel Algorithms with Optimal Speedup for Bounded Treewidth.

[BibT_eX]

[DOI]

Torben Hagerup

SIAM J. Comput., 1998

Treewidth and Minimum Fill-in on d-Trapezoid Graphs.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 1998

Linear-Time Register Allocation for a Fixed Number of Registers.

[BibT_eX]

[DOI]

Jens Gustedt

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Tree Decompositions of Small Diameter.

[BibT_eX]

[DOI]

Torben Hagerup

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997

Domino Treewidth.

[BibT_eX]

[DOI]

Joost Engelfriet

J. Algorithms, 1997

Fast Partitioning l-Apex Graphs with Application to Approximating Maximum Induced-Subgraph Problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

It is Hard to Know when Greedy is Good for Finding Independent Sets.

[BibT_eX]

[DOI]

Koichi Yamazaki

Inf. Process. Lett., 1997

Triangulating Planar Graphs while Minimizing the Maximum Degree.

[BibT_eX]

[DOI]

Goos Kant

Inf. Comput., 1997

On Interval Routing Schemes and Treewidth.

[BibT_eX]

[DOI]

Richard B. Tan

Inf. Comput., 1997

Treewidth for Graphs with Small Chordality.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1997

Parallel Algorithms for Treewidth Two.

[BibT_eX]

[DOI]

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

Treewidth: Algorithmic Techniques and Results.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Constructive Linear Time Algorithms for Branchwidth.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 1996

On Intervalizing K-colored Graphs for DNA Physical Mapping.

[BibT_eX]

[DOI]

Babette van Antwerpen-de Fluiter

Discret. Appl. Math., 1996

Parallel Algorithms for Series Parallel Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1996

Finite-State Computability of Annotations of Strings and Trees.

[BibT_eX]

[DOI]

Patricia A. Evans

Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

Reduction Algorithms for Constructing Solutions in Graphs with Small Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995

Restrictions of Graph Partition Problems. Part I.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

The Parameterized Complexity of Sequence Alignment and Consensus.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

Treewidth and Pathwidth of Permutation Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1995

W[2]-hardness of precedence constrained K-processor scheduling.

[BibT_eX]

[DOI]

Oper. Res. Lett., 1995

Complexity Aspects of Two-Dimensional Data Compression.

[BibT_eX]

Teofilo F. Gonzalez

Nord. J. Comput., 1995

Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree.

[BibT_eX]

[DOI]

John R. Gilbert

Hjálmtyr Hafsteinsson

J. Algorithms, 1995

Parameterized complexity analysis in computational biology.

[BibT_eX]

[DOI]

Comput. Appl. Biosci., 1995

Intervalizing k-Colored Graphs.

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

Shlomo Moran

Manfred K. Warmuth

Inf. Comput., January, 1994

Trade-Offs in Non-Reversing Diameter.

[BibT_eX]

Nicola Santoro

Nord. J. Comput., 1994

On Disjoint Cycles.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 1994

Scheduling with Incompatible Jobs.

[BibT_eX]

[DOI]

Gerhard J. Woeginger

Discret. Appl. Math., 1994

Improved Self-reduction Algorithms for Graphs with Bounded Treewidth.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1994

Domino Treewith (Extended Abstract).

[BibT_eX]

[DOI]

Joost Engelfriet

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

Ranking of Graphs.

[BibT_eX]

[DOI]

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

Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy.

[BibT_eX]

[DOI]

Michael T. Hallett

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.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1994

1993

Complexity of Path-Forming Games.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

The Pathwidth and Treewidth of Cographs.

[BibT_eX]

[DOI]

Rolf H. Möhring

SIAM J. Discret. Math., 1993

Book review.

[BibT_eX]

[DOI]

ZOR Methods Model. Oper. Res., 1993

A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 1993

On Linear Time Minor Tests with Depth-First Search.

[BibT_eX]

[DOI]

J. Algorithms, 1993

A Tourist Guide through Treewidth.

[BibT_eX]

[DOI]

Acta Cybern., 1993

Dynamic Algorithms for Graphs with Treewidth 2.

[BibT_eX]

[DOI]

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

On Reduction Algorithms for Graphs with Small Treewidth.

[BibT_eX]

[DOI]

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

On the Complexity of Scheduling Incompatible Jobs with Unit-Times.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

Kayles on Special Classes of Graphs - An Application of Sprague-Grundy Theory.

[BibT_eX]

[DOI]

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

Testing Superperfection of k-Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1992

Approximating Treewidth and Pathwidth of some Classes of Perfect Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

Two Strikes Against Perfect Phylogeny.

[BibT_eX]

[DOI]

Tandy J. Warnow

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

Some Lower Bound Results for Decentralized Extrema-Finding in Rings of Processors.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

On the Complexity of Some Coloring Games.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 1991

Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height.

[BibT_eX]

[DOI]

John R. Gilbert

Hjálmtyr Hafsteinsson

Proceedings of the 17th International Workshop, 1991

Planar Graph Augmentation Problems (Extended Abstract).

[BibT_eX]

[DOI]

Goos Kant

Proceedings of the Algorithms and Data Structures, 1991

Better Algorithms for the Pathwidth and Treewidth of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Complexity Aspects of Map Compression.

[BibT_eX]

[DOI]

Teofilo F. Gonzalez

Proceedings of the IEEE Data Compression Conference, 1991

1990

The Complexity of Finding Uniform Emulations on Paths and Ring Networks

[BibT_eX]

[DOI]

Inf. Comput., May, 1990

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

[BibT_eX]

[DOI]

J. Algorithms, 1990

Bit-Optimal Election in Synchronous Rings.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

Computational complexity of norm-maximization.

[BibT_eX]

[DOI]

Comb., 1990

1989

The Classification of Coverings of Processor Networks.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 1989

Achromatic Number is NP-Complete for Cographs and Interval Graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1989

On Linear Time Minor Tests and Depth First Search.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 1989

Distributed Computing on TRansitive Networks: The Thorus.

[BibT_eX]

[DOI]

Paul Beame

Proceedings of the STACS 89, 1989

1988

The Complexity of Finding Uniform Emulations on Fixed Graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

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

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

Some Classes of Graphs with Bounded Treewidth.

[BibT_eX]

Bull. EATCS, 1988

NC-Algorithms for Graphs with Small Treewidth.

[BibT_eX]

[DOI]

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

Dynamic Programming on Graphs with Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

1987

Diameter increase caused by edge deletion.

[BibT_eX]

[DOI]

Anneke A. Schoone

J. Graph Theory, 1987

New Lower Bounds for Distributed Leader Finding in Asynchronous Rings of Processors.

[BibT_eX]

[DOI]

Proceedings of the GI, 1987

1986

Simulation of Large Networks on Smaller Networks

[BibT_eX]

[DOI]

Inf. Control., December, 1986

Improved Diameter Bounds for Altered Graphs.

[BibT_eX]

[DOI]

Anneke A. Schoone

Proceedings of the Graphtheoretic Concepts in Computer Science, International Workshop, 1986

New Upperbounds for Decentralized Extrema-Finding in a Ring of Processors.

[BibT_eX]

[DOI]