Hans L. Bodlaender

Research interests

Publications

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

  SIAM Journal on Computing · 2016 · https://doi.org/10.1137/130947374

• Kernelization Lower Bounds by Cross-Composition

  SIAM Journal on Discrete Mathematics · 2014 · https://doi.org/10.1137/120880240

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

  Information and Computation · 2014 · https://doi.org/10.1016/j.ic.2014.12.008

• Kernel bounds for disjoint cycles and disjoint paths

  Theoretical Computer Science · 2011 · https://doi.org/10.1016/j.tcs.2011.04.039

• On problems without polynomial kernels

  Journal of Computer and System Sciences · 2009 · https://doi.org/10.1016/j.jcss.2009.04.001

• Treewidth computations I. Upper bounds

  Information and Computation · 2009 · https://doi.org/10.1016/j.ic.2009.03.008

• (Meta) Kernelization

  Journal · 2009 · https://doi.org/10.1109/focs.2009.46

• Kernelization: New Upper and Lower Bound Techniques

  Lecture notes in computer science · 2009 · https://doi.org/10.1007/978-3-642-11269-0_2

• Combinatorial Optimization on Graphs of Bounded Treewidth

  The Computer Journal · 2007 · https://doi.org/10.1093/comjnl/bxm037

• Parameterized and Exact Computation

  Lecture notes in computer science · 2006 · https://doi.org/10.1007/11847250

• Discovering Treewidth

  Lecture notes in computer science · 2005 · https://doi.org/10.1007/978-3-540-30577-4_1

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

  Algorithmica · 2002 · https://doi.org/10.1007/s00453-001-0116-5

• A partial k-arboretum of graphs with bounded treewidth

  Theoretical Computer Science · 1998 · https://doi.org/10.1016/s0304-3975(97)00228-4

• Treewidth: Algorithmic techniques and results

  Lecture notes in computer science · 1997 · https://doi.org/10.1007/bfb0029946

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

  Journal of Algorithms · 1996 · https://doi.org/10.1006/jagm.1996.0049

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

  SIAM Journal on Computing · 1996 · https://doi.org/10.1137/s0097539793251219

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

  Journal of Algorithms · 1995 · https://doi.org/10.1006/jagm.1995.1009

• The Pathwidth and Treewidth of Cographs

  SIAM Journal on Discrete Mathematics · 1993 · https://doi.org/10.1137/0406014

• On Linear Time Minor Tests with Depth-First Search

  Journal of Algorithms · 1993 · https://doi.org/10.1006/jagm.1993.1001

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

  Journal · 1993 · https://doi.org/10.1145/167088.167161

• A tourist guide through Treewidth

  Journal · 1992

• Two strikes against perfect phylogeny

  Lecture notes in computer science · 1992 · https://doi.org/10.1007/3-540-55719-9_80

• ON THE COMPLEXITY OF SOME COLORING GAMES

  International Journal of Foundations of Computer Science · 1991 · https://doi.org/10.1142/s0129054191000091

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

  Journal of Algorithms · 1990 · https://doi.org/10.1016/0196-6774(90)90013-5

• Dynamic programming on graphs with bounded treewidth

  Lecture notes in computer science · 1988 · https://doi.org/10.1007/3-540-19488-6_110

Current projects

No projects listed.