Search filters

List of works by Hans L. Bodlaender

(Meta) Kernelization

(Meta) Kernelization

A $c^k n$ 5-Approximation Algorithm for Treewidth

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

article by Emgad H. Bachoore & Hans L. Bodlaender published 2006 in Lecture Notes in Computer Science

A Cubic Kernel for Feedback Vertex Set and Loop Cutset

A Kernel for Convex Recoloring of Weighted Forests

A Linear Kernel for Planar Feedback Vertex Set

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

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

A Local Search Algorithm for Branchwidth

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

scholarly article by Hans L. Bodlaender et al published 21 January 2011 in Theory of Computing Systems

A Note on Rectilinearity and Angular Resolution

A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs

A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors

A faster parameterized algorithm for Pseudoforest Deletion

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

A linear time algorithm for finding tree-decompositions of small treewidth

A partial k-arboretum of graphs with bounded treewidth

scientific article (publication date: December 1998)

Achromatic number is NP-complete for cographs and interval graphs

Algorithms for Graphs Embeddable with Few Crossings per Edge

scientific article (publication date: 2 August 2007)

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

Approximating treewidth and pathwidth of some classes of perfect graphs

scientific article (publication date: 1992)

Approximation of pathwidth of outerplanar graphs

Better algorithms for the pathwidth and treewidth of graphs

Beyond NP-completeness for problems of bounded width (extended abstract)

Characterizing width two for variants of treewidth

Clustering with Partial Information

article published in Lecture Notes in Computer Science

Clustering with partial information

article by Hans L. Bodlaender et al published February 2010 in Theoretical Computer Science

Complexity Results for the Spanning Tree Congestion Problem

Complexity of path-forming games

Computational complexity of norm-maximization

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

Cutwidth I: A linear time fixed parameter algorithm

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

Definability equals recognizability fork-outerplanar graphs andl-chordal partialk-trees

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

article by Hans L. Bodlaender et al published 5 December 2017 in Algorithmica

Derivation of algorithms for cutwidth and related graph layout parameters

scholarly article by Hans L. Bodlaender et al published June 2009 in Journal of Computer and System Sciences

Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

scholarly article by Hans L. Bodlaender et al published 2013 in Lecture Notes in Computer Science

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution

article published in 2009

Dynamic programming on graphs with bounded treewidth

scientific article (publication date: 1988)

Editorial

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

scholarly article by Frederic Dorn et al published 2005 in Lecture Notes in Computer Science

Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions

Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

scientific article (publication date: September 1996)

Equitable colorings of bounded treewidth graphs

Erratum to: Editorial

scholarly article published in Algorithmica

Exact Algorithms for Edge Domination

Exact Algorithms for Edge Domination

scholarly article by Johan M. M. van Rooij & Hans L. Bodlaender published 2008 in Lecture Notes in Computer Science

Exact Algorithms for Intervalizing Colored Graphs

scholarly article by Hans L. Bodlaender & Johan M. M. van Rooij published 2011 in Lecture Notes in Computer Science

Exact Algorithms for Intervalizing Coloured Graphs

scholarly article by Hans L. Bodlaender & Johan M. M. van Rooij published 15 March 2015 in Theory of Computing Systems

Exact Algorithms for Kayles

scholarly article by Hans L. Bodlaender & Dieter Kratsch published 2011 in Lecture Notes in Computer Science

Exact algorithms for Kayles

Exact algorithms for dominating set

scholarly article by Johan M.M. van Rooij & Hans L. Bodlaender published October 2011 in Discrete Applied Mathematics

Faster Algorithms on Branch and Clique Decompositions

Faster Parameterized Algorithms for Minimum Fill-In

Faster Parameterized Algorithms for Minimum Fill-in

Finding a Δ-regular supergraph of minimum order

Finite-state computability of annotations of strings and trees (extended abstract)

Fixed-Parameter Tractability and Characterizations of Small Special Treewidth

Fixed-Parameter Tractability of Treewidth and Pathwidth

scientific article

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

scholarly article by Hans L. Bodlaender & Marc van Kreveld published December 2015 in Information Processing Letters

Graphs with Branchwidth at Most Three

Improved Lower Bounds for Graph Embedding Problems

Improved self-reduction algorithms for graphs with bounded treewidth

Improved self-reduction algorithms for graphs with bounded treewidth

scholarly article by Hans L. Bodlaender published 1990 in Lecture Notes in Computer Science

Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint

article published in 2008

Intervalizing k-colored graphs

Isomorphism for graphs of bounded distance width

Kayles and Nimbers

Kernel Bounds for Disjoint Cycles and Disjoint Paths

Kernel Bounds for Path and Cycle Problems

Kernel Bounds for Structural Parameterizations of Pathwidth

Kernel bounds for disjoint cycles and disjoint paths

Kernel bounds for path and cycle problems

Kernelization Lower Bounds by Cross-Composition

article

Kernelization, Exponential Lower Bounds

Kernelization: New Upper and Lower Bound Techniques

article by Hans L. Bodlaender published 2009 in Lecture Notes in Computer Science

Lower Bounds for Kernelization

NC-algorithms for graphs with small treewidth

scholarly article by Hans L. Bodlaender published 1989 in Lecture Notes in Computer Science

On Game-Theoretic Models of Networks

On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion

On Problems without Polynomial Kernels (Extended Abstract)

On Stopping Evidence Gathering for Diagnostic Bayesian Networks

article

On algorithms for ( P 5 ,gem)-free graphs

article published in 2005

On exact algorithms for treewidth

On exploring always-connected temporal graphs of small pathwidth

scholarly article by Hans L. Bodlaender & Tom C. van der Zanden published February 2019 in Information Processing Letters

On linear time minor tests and depth first search

On problems without polynomial kernels

On switching classes, NLC-width, cliquewidth and treewidth

On the Maximum Weight Minimal Separator

On the complexity of some coloring games

On the maximum cardinality search lower bound for treewidth

article by Hans L. Bodlaender & Arie M.C.A. Koster published June 2007 in Discrete Applied Mathematics

On the minimum corridor connection problem and other generalized geometric problems

Online topological ordering

PREPROCESSING RULES FOR TRIANGULATION OF PROBABILISTIC NETWORKS*

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

Parallel algorithms for series parallel graphs

scholarly article by Hans L. Bodlaender & Babette Fluiter published 1996 in Lecture Notes in Computer Science

Parallel algorithms with optimal speedup for bounded treewidth

scholarly article by Hans L. Bodlaender & Torben Hagerup published 1995 in Lecture Notes in Computer Science

Parameterized Complexity of the Spanning Tree Congestion Problem

Partition Into Triangles on Bounded Degree Graphs

Partition into Triangles on Bounded Degree Graphs

Planar Capacitated Dominating Set Is W[1]-Hard

Planar graph augmentation problems

Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

scholarly article by Hans L. Bodlaender published 1988 in Lecture Notes in Computer Science

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

article published in 2013

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

Problems Hard for Treewidth but Easy for Stable Gonality

Quadratic Kernelization for Convex Recoloring of Trees

Radio Labeling with Preassigned Frequencies

Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality

Recognizing Hyperelliptic Graphs in Polynomial Time

Reduction Algorithms for Graphs of Small Treewidth

scholarly article by Hans L. Bodlaender & Babette van Antwerpen-de Fluiter published June 2001 in Information and Computation

Restrictions of graph partition problems. Part I

Robust Recoverable Path Using Backup Nodes

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

Safe Reduction Rules for Weighted Treewidth

Safe separators for treewidth

Scheduling of pipelined operator graphs

scientific article published in 2012

Scheduling with incompatible jobs

Spanning tree congestion of k -outerplanar graphs

Speeding Up Dynamic Programming with Representative Sets

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

Subexponential Time Algorithms for Finding Small Tree and Path Decompositions

Testing superperfection of k-trees

The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks

The Fine Details of Fast Dynamic Programming over Tree Decompositions

The Homogeneous Broadcast Problem in Narrow and Wide Strips

The Valve Location Problem in Simple Network Topologies

article by Hans L. Bodlaender et al published August 2010 in Informs Journal on Computing

The Valve Location Problem in Simple Network Topologies

The algorithmic theory of treewidth

The classification of coverings of processor networks

The complexity of coloring games on perfect graphs

The complexity of finding uniform emulations on fixed graphs

The complexity of finding uniform emulations on paths and ring networks

The distributed bit complexity of the ring: From the anonymous to the non-anonymous case

The parameterized complexity of sequence alignment and consensus

The pathwidth and treewidth of cographs

Tree decompositions with small cost

article published in 2005

Treewidth Lower Bounds with Brambles

Treewidth and Pathwidth of Permutation Graphs

Treewidth computations I. Upper bounds

Treewidth computations II. Lower bounds

Treewidth of Graphs

Treewidth of Graphs

Treewidth: Computational Experiments

Triangulating planar graphs while minimizing the maximum degree

Two strikes against perfect phylogeny

scholarly article by Hans L. Bodlaender et al published 1992 in Lecture Notes in Computer Science

Typical Sequences Revisited — Computing Width Parameters of Graphs

scientific article published on 26 March 2021

Vertex Cover Kernelization Revisited

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

article by Hans L. Bodlaender & Michael R. Fellows published September 1995 in Operations Research Letters

Wooden Geometric Puzzles: Design and Hardness Proofs

Paulina is supported by:

About Paulina

Help