Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint ⋆ Abstract (2009)
Hans L. Bodlaender, Richard B. Tan, ...
We study the integer maximum flow problem on wireless sensor networks with energy constraint. In this problem, sensor nodes gather data and then relay them to a base station, before they run out of...
Bodlaender, Hans L., Fomin, Fedor V., Lokshtanov, Daniel, Penninkx, Eelko, Saurabh, Saket, Thilikos, Dimitrios M.
Polynomial time preprocessing to reduce instance size is one of the most commonly deployed heuristics to tackle computationally hard problems. In a parameterized problem, every instance I comes with...
doi:10.1093/comjnl/bxm037 Combinatorial Optimization on Graphs of Bounded Treewidth (2008)
There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems,...
Konrad-Zuse-Zentrum fu¨r Informationstechnik Berlin (2008)
Thomas Wolle, Hans L. Bodlaender, Degree-based Treewidth, Lower Bounds, Degree-based Treewidth, ...
Abstract. Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving...
Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P4’s (2008)
Hans L. Bodlaender, Marisa Gutierrez, Ton Kloks, Rolf Niedermeier
Abstract. The simple max-cut problem is as follows: given a graph, find a partition of its vertex set into two disjoint sets, such that the number of edges having one endpoint in each set is as large...
Konrad-Zuse-Zentrum für Informationstechnik Berlin (2008)
Hans L. Bodlaender, Alexander Grigoriev, Treewidth Lower, Bounds Brambles, Treewidth Lower, ...
In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph G is the maximum order of a bramble of G...
IOS Press Relaxed Update and Partition Network Games (2008)
Hans L. Bodlaender, Bakhadyr Khoussainov
Abstract. In this paper, we study the complexity of deciding which player has a winning strategy in certain types of McNaughton games. These graph games can be used as models for computational...
A generic NP-hardness proof for a variant of graph coloring (2008)
Abstract: In this note, a direct proof is given of the NP-completeness of a variant of Graph Coloring, i.e., a generic proof similar to the proof of Cook of the NPcompleteness of Satisfiability....
Konrad-Zuse-Zentrum fu¨r Informationstechnik Berlin (2008)
Frank Van, Den Eijkhof, Hans L. Bodlaender, Frank Eijkhoft, Hans L. Bodlaender, ...
Safe reduction rules for weighted treewidth*
Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set (2008)
The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems, like Dominating Set and Independent Set. In this paper, we propose to use...
Emgad H. Bachoore, Hans L. Bodlaender, Emgad H. Bachoore, Hans L. Bodlaender
www.cs.uu.nl
www.cs.uu.nl 1 New Upper Bound Heuristics for Treewidth * (2008)
Emgad H. Bachoore, Hans L. Bodlaender, Emgad H. Bachoore, Hans L. Bodlaender
In this paper, we introduce and evaluate some heuristics to find an upper bound on the treewidth of a given graph. Each of the heuristics selects the vertices of the graph one by one, building an...
Open Problems in Parameterized and Exact Computation — IWPEC 2006 (2008)
Hans L. Bodlaender, Leizhen Cai, Jianer Chen, Michael R. Fellows, Jan Arne Telle, Dániel Marx, ...
www.cs.uu.nl
On interval routing schemes (2008)
Hans L. Bodlaender, Jan Van Leeuwen, Richard Tan, Dimitrios M. Thilikos
Abstract. In this paper, we investigate which processor networks allow klabel Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each xed k 1, the class of...
www.cs.uu.nl Pre-Processing Rules for Triangulation of Probabilistic Networks £ (2008)
The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network’s graph. In this paper, we show that pre-processing can help in finding...
Wooden Geometric Puzzles: Design and Hardness Proofs (2008)
Hans L. Bodlaender, Marc Van Kreveld, Günter Rote, Gerard Tel, Helmut Alt, Hans L. Bodlaender, ...
We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the solution...
www.cs.uu.nl A Note on Edge Contraction (2008)
Thomas Wolle, Hans L. Bodlaender, Thomas Wolle, Hans L. Bodlaender
Abstract. Contracting an edge is the operation that introduces a new vertex that is adjacent to all vertices the endpoints of the contracted edge are adjacent to, and then deletes the endpoints of...
that Intervalizing Colored Graphs, Triangulating Colored Graphs, and (2008)
Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett
In this paper, we consider the complexity ofanumber of combinatorial problems; namely, Intervalizing Colored Graphs (DNA physical mapping), Triangulating
www.cs.uu.nl Online Topological Ordering (2008)
Irit Katriel, Hans L. Bodlaender, Irit Katriel, Hans L. Bodlaender
Abstract. It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O(min{m 3/2 log n, m 3/2 + n 2 log n})...
www.cs.uu.nl Discovering Treewidth ∗ (2008)
Discovering Treewidth, Hans L. Bodlaender, Hans L. Bodlaender
Treewidth is a graph parameter with several interesting theoretical and practical applications. This survey reviews algorithmic results on determining the treewidth of a given graph, and finding a...
Helmut Alt, Hans L. Bodlaender, Marc Kreveld, Gerard Tel, Gerard Tel
Abstract We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the...
www.cs.uu.nl On the Maximum Cardinality Search Lower (2008)
Hans L. Bodlaender, Bound For Treewidth
The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An...
Thomas Wolle, Hans L. Bodlaender, Degree-based Treewidth, Lower Bounds, ...
Abstract. Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving...
Journal of Graph Algorithms and Applications (2008)
Hans L. Bodlaender, Ton Kloks, Dieter Kratsch, Haiko Müller
vol. 2, no. 5, pp. 1–23 (1998) Treewidth and minimum fill-in on d-trapezoid graphs
www.cs.uu.nl A Note on Contraction Degeneracy ⋆ (2008)
Thomas Wolle, Hans L. Bodlaender, Thomas Wolle, Hans L. Bodlaender
Abstract. The parameter contraction degeneracy — the maximum minimum degree over all minors of a graph — is a treewidth lower bound and was first defined in [3]. In experiments it was shown that...
Hans L. Bodlaender, Alexander Grigoriev, Treewidth Lower, Bounds Brambles
In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph G is the maximum order of a bramble of G...
Reduction Algorithms for Graphs (2008)
Small Treewidth, Hans L. Bodlaender, Babette De Fluiter
This paper presents some new ideas and results on graph reduction applied to graphs with bounded treewidth. Arnborg et al. [2] have shown that many decision problems on graphs can be solved in linear...
Treewidth Lower Bounds, Hans L. Bodlaender, Thomas Wolle, Treewidth Lower Bounds
Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the...
Parallel Algorithms for Treewidth Two Babette de Fluiter Centre for Quantitative Methods (2008)
In this paper we present a parallel algorithm that decides whether a graph G has treewidth at most two, and if so, construct a tree decomposition or path decomposition of minimum width of G. The...
www.cs.uu.nl On Algorithms for (P5,Gem)-Free Graphs (2008)
Hans L. Bodlaender, Andreas Brandstädt, Dieter Kratsch, Michaël Rao, Jeremy Spinrad, Städt Dieter Kratsch, ...
A graph is (P5,gem)-free, when it does not contain P5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced...
Intervalizing Sandwich Graphs (2008)
Babette Fluiter, Hans L. Bodlaender
In this report, we consider the following problem: given two graphs G1 =(V;E1) and G2 =(G;E2) such that E1 E2, is there an interval graph G 0 =(V;E 0) with maximum clique size at most three such that...
Interval Routing and Minor-Monotone Graph Parameters ∗ (2008)
Erwin M. Bakker, Hans L. Bodlaender, Richard B. Tan
We survey a number of minor-monotone graph parameters and their relationship to the complexity of routing on graphs. In particular we compare the interval routing parameters κslir(G) andκsir(G)...
Isomorphism for Graphs of Bounded Distance Width (2008)
Koichi Yamazaki, Hans L. Bodlaender, Babette De Fluiter, Dimitrios M. Thilikos
In this paper, we study the Graph Isomorphism problem on graphs of bounded treewidth, bounded degree or bounded bandwidth. Graph Isomorphism can be solved in polynomial time for graphs of bounded...
The Valve Location Problem in Simple Network Topologies (2008)
Hans L. Bodlaender, Alexander Grigoriev, Nadejda V. Grigorieva, Albert Hendriks, Albert Hendriks
To control possible spills in liquid or gas transporting pipe systems, the systems are usually equipped with shutoff valves. In case of an accidental leak these valves separate the system into a...
Clustering with partial information ∗ (2008)
Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, Frances Rosamond, ...
The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that...
Complexity Results for Local Monotonicity in Probabilistic Networks (2008)
Johan Kwisthout, Hans L. Bodlaender, Gerard Tel, Johan Kwisthout, Hans L. Bodlaender, Gerard Tel
Often, monotonicity is a desirable property of probabilistic networks. For example, when medical knowledge in a particular domain dictates that more severe symptoms increase the likeliness of a more...
Treewidth Computations I. Upper Bounds (2008)
For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. This paper gives an overview of...
Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo
Transformations give evidence for non-existence of polynomial kernels
Open Problems in Parameterized and Exact Computation — (2008)
Hans L. Bodlaender, Erik D. Demaine, Michael R. Fellows, Jiong Guo, Danny Hermelin, Daniel Lokshtanov, ...
www.cs.uu.nl
Faster parameterized algorithms for Minimum Fill-In (2008)
Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger, Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger
Faster parameterized algorithms for Minimum Fill-In
57. Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set (2008)
The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems, like Dominating Set and Independent Set. In this paper, we propose to use...
Combinatorial Optimization on Graphs of Bounded Treewidth (2008)
There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems,...
Clustering with partial information (2008)
Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, Frances Rosamond, ...
The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that...
Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger, Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger
We present two parameterized algorithms for the Minimum Fill-In problem, also known as Chordal Completion: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a...
Dimitrios M. Thilikos, Hans L. Bodlaender
We prove that, for any fixed k, one can construct a linear time algorithm that checks if a graph has branchwidth k and, if so, outputs a branch decomposition of minimum width. 1
Isomorphism for Graphs of Bounded Distance Width (2007)
Koichi Yamazaki Hans, Hans L. Bodlaender, Babette De Fluiter, Dimitrios M. Thilikos
In this paper, we study the Graph Isomorphism problem on graphs of bounded treewidth, bounded degree or bounded bandwidth. Graph Isomorphism can be solved in polynomial time for graphs of bounded...
Finding a Minimal Tree in a Polygon with its Medial Axis (2007)
Herman J. Haverkort, Hans L. Bodlaender
In order to solve a problem arising when generalizing topographical maps, we consider the following problem for simple polygons, i.e., coherent polygons without holes. Some edges of the polygon may...
Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett, H. Todd Wareham, Tandy J. Warnow
In this paper, we consider the complexity of a number of combinatorial problems; namely, Intervalizing Colored Graphs (DNA physical mapping), Triangulating Colored Graphs (perfect phylogeny),...
Parallel Algorithms for Partial Two-Trees and for Blocks of Partial k-Trees (2007)
Babette De Fluiter, Hans L. Bodlaender
. In this paper we present a parallel algorithm which, given a graph G of bounded treewidth (i.e. G is a partial k-tree for some fixed k 1), splits G in its blocks (biconnected components)....
Treewidth and Minimum Fill-in on (2007)
Trapezoid Graphs, Hans L. Bodlaender, Dieter Kratsch, Haiko Muller
We show that the minimum fill-in and the minimum interval graph completion of a d-trapezoid graph can be computed in time O(n d ). We also show that the treewidth and the pathwidth of a d-trapezoid...
Hans L. Bodlaender, Marisa Gutierrez, Rolf Niedermeier
Abstract. The simple max-cut problem is as follows: given a graph, nd a partition of its vertex set into two disjoint sets, such that the number of edges having one endpoint in each set is as large...
Pre-processing rules for triangulation of probabilistic networks (2007)
Hans L. Bodlaender, Hans L. Bodlaender
The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding...
Safe reduction rules for weighted treewidth Frank van den Eijkhof (2007)
Hans L. Bodlaender, Hans L. Bodlaender
www.cs.uu.nl Safe reduction rules for weighted treewidth
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c p
Hans L. Bodlaender, Dieter Kratsch
vol. 2, no. 5, pp. 1-23 (1998) Treewidth and minimum ll-in on d-trapezoid graphs
Hans L. Bodlaender, Hans L. Bodlaender, Hans L. Bodlaender
In this paper we study the complexity of graph decision problems, restricted to the class of graphs with treewidth _ the class of partial k-trees), for fixed k. We introduce two classes of graph...
In this paper we give, for all constants k, l, explicit algorithms, that given a graph G = (V; E) with a tree-decomposition of G with treewidth at most l, decide whether the treewidth (or pathwidth)...
Vakgroep Tnformafica, Paul W. Beame, Paul W. Beame, Paul W. Beame, Hans L. Bodlaender, Hans L. Bodlaender, ...
We identify the class of transitive networks as being of particular interest for dis-tributed computation with known topology. This class includes the ring and the complete network as well as the...
On interval routing schemes (2007)
Hans L. Bodlaender, Jan Van Leeuwen, Richard Tan, Dimitrios M. Thilikos
Abstract. In this paper, we investigate which processor networks allow k-label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixed k 1, the class...
ON LINEAR TIME MINOR TESTS (2007)
Vakgroep Informatica, Hans L. Bodlaender, Hans L. Bodlaender, Hans L. Bodlaender
Recent results on graph minors make it desirable to have efficient algorithms, that for a fixed set of graphs {H,...,He}, test whether a given graph G contains at least one graph Hi as a minor. In...
Relaxed Update and Partition Network Games (2007)
Michaelj Dinneen, Bakhadir Khoussainov, Hans L. Bodlaender, Hans L. Bodlaender, Michael J. Dinneen, Bakhadyr Khoussainov
In this paper, we study the complexity of deciding which player has a winning strategy in certain types of McNaughton games. These graph games can be used as models for computational problems and...
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Harold T. Wareham
The Longest common subsequence problem is examined from the point of view of parameterized computational complexity. There are several different ways in which parameters enter the problem, such as...
Intervalizing Sandwich Graphs (2007)
Babette Fluiter, Hans L. Bodlaender
In this report, we consider the following problem: given two graphs G 1 = (V;E 1) and G 2 = (G;E 2) such that E 1 ` E 2, is there an interval graph G 0
Parallel Algorithms for Treewidth Two (2007)
Babette De Fluiter, Hans L. Bodlaender
In this paper we present a parallel algorithm that decides whether a graph G has treewidth at most two, and if so, construct a tree decomposition or path decomposition of minimum width of G. The...
Hans L. Bodlaender, Hans L. Bodlaender, Dieter Kratsch, Dieter Kratsch, Dieter Kratsch I
complexity of coloring games on perfect graphs
A generic NP-hardness proof for a variant of graph coloring (2007)
A generic NP-hardness proof for a variant of Graph Coloring* Hans L. Bodlaender t In this note, a direct proof is given of the NP-completeness of a variant of GRAPH COLORING, i.e., a generic proof is...
The Distributed Bit Complexity of the Ring: (2007)
Vakgroep Nformatica, Hans L. Bodlaender, Hans L. Bodlaender, Hans L. Bodlaender, Shlomo Moran, Shlomo Moran, ...
From the Anonymous to the Non-anonymous Case
Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett, H. Todd Wareham, Tandy J. Warnow
In this paper, we consider the complexity of a number of combinatorial problems; namely, Intervalizing Colored Graphs (DNA physical mapping), Triangulating
Triangulating Planar Graphs While (2007)
Goos Kant, Goos Kant, Goos Kant, Hans L. Bodlaender, Hans L. Bodlaender, Hans L. Bodlaender
In this paper we study the problem of triangulating a planar graph G while minimizing the maximum degree A(G) of the resulting triangulated planar graph G. It is shown that this problem is...
Treewidth and Small Separators for Graphs with (2007)
Small Chordality, Hans L. Bodlaender, Dimitris M. Thilikos
A graph G k-chordal, if it does not contain chordless cycles of length larger than k. The chordality cl of a graph G is the minimum k for which G is k-chordal. The degeneracy or the width of a graph...
Hans L. Bodlaender, Hans L. Bodlaender, Hajo J. Broersma, Hajo J. Broersma, Fedor V. Fomin, Fedor V. Fomin, ...
www.cs.uu.nl Radio labeling with pre-assigned frequencies
graphs with Applications to Approximating Maximum Induced-Subgraph Problems (2007)
Dimitrios M. Thilikos, Hans L. Bodlaender
l-apex
Hans L. Bodlaender, Dieter Kratsch, Haiko Muller
We show that the minimum fill-in and the minimum interval graph completion of a d-trapezoid graph can be computed in time O(n d). We also show that the treewidth and the pathwidth of a d-trapezoid...
NC-ALGORITHMS FOR GRAPHS WITH (2007)
Vakgroep Informatica, Small Treewidth, Small Treewidth, Hans L. Bodlaender, Hans L. Bodlaender
Let G = (V, E) be a graph. A tree-decomposition of G is a pair ({Xdi E I}, T = (I, F)), with {Xdi E [} a fatally of subsets of V and T a tree, with the following properties: Ux=v For every edge e =...
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c p
Hans L. Bodlaender, Stan P. M, Van Hoesel, Koster Hans, ...
graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this...
Hans L. Bodlaender, Klaus Jansen, Gerhard J. Woeginger
Abstract. We consider scheduling problems in a multiprocessor system with incompatible jobs (two incompatible jobs cannot be processed by the same machine). We consider the problem to minimize the...
Nordic Journal of Computing ON THE COMPLEXITY OF THE MAXIMUM CUT PROBLEM (2007)
Hans L. Bodlaender, Klaus Jansen
Abstract. The complexity of the simple max cut problem is investigated for several special classes of graphs. It is shown that this problem is NP-complete when restricted to one of the following...
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
Constructive linear time algorithms for small
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
Constructive linear time algorithms for small
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
polynomial time algorithm for the cutwidth of bounded degree graphs
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
polynomial time algorithm for the cutwidth of bounded degree graphs
Hans L. Bodlaender, John R. Gilbert
Various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex separators of graphs. The...
The Valve Location Problem in Simple Network Topologies (2007)
Bodlaender, Hans L., Grigoriev, Alexander, Grigorieva, Nadedja V., Hendriks, Albert
The Valve Location Problem (2007)
Bodlaender, Hans L., Grigoriev, Alexander, Grigorieva, Nadejda V., Hendriks, Albert
Quadratic Kernelization for Convex Recoloring of Trees (2007)
Bodlaender, Hans L., Fellows, Michael R., Langston, Michael A., Ragan, Mark A., Rosamond, Frances A., Weyer, Mark
The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For input consisting of a vertex-colored tree T, the problem is...
Exact Algorithms for Edge Domination ∗ (2007)
Van Rooij, Hans L. Bodlaender, Hans L. Bodlaender
An edge dominating set in a graph G = (V, E) is a subset of the edges D ⊆ E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of...
On problems without polynomial kernels (2007)
Hans L. Bodlaender, Hans L. Bodlaender, Rodney G. Downey, Rodney G. Downey, Michael R. Fellows, Michael R. Fellows, ...
Abstract. Kernelization is a strong and widely-applied technique in the design of fixed-parameter algorithms. In a nutshell, a kernelization algorithm is a polynomial-time transformation that...
Quadratic kernelization for convex recoloring of trees (2007)
Hans L. Bodlaender, Hans L. Bodlaender, Michael R. Fellows, Michael R. Fellows, Michael A. Langston, Michael A. Langston, ...
Abstract. The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the...
A cubic kernel for feedback vertex set (2007)
Hans L. Bodlaender, Hans L. Bodlaender
The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. [7], we show that this problem has akernelwithO(k 3) vertices, i.e., there is...
On problems without polynomial kernels (2007)
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin
Abstract. Kernelization is a strong and widely-applied technique in parameterized complexity. In a nutshell, a kernelization algorithm, or simply a kernel, is a polynomial-time transformation that...
Convex Recoloring of Leaf-Colored Trees (2006)
Emgad H. Bachoore, Emgad H. Bachoore, Hans L. Bodlaender, Hans L. Bodlaender
A coloring of the leaves of a tree T is called convex, if it is possible to give each internal node a color, such that for each color, the set of nodes with that color forms a subtree of T ....
A branch and bound algorithm for exact, upper, and lower bounds on treewidth (2006)
Emgad H. Bachoore, Hans L. Bodlaender
In this paper, a branch and bound algorithm for computing the treewidth of a graph is presented. The method incorporates extensions of existing results, and uses new pruning and reduction rules,...
Algorithmic Techniques and Results (2006)
Emgad Bachoore Hans, Emgad Bachoore, Hans L. Bodlaender, Hans L. Bodlaender
From the analysis of algorithms for probabilistic networks, it is known that a tree decomposition of the minimum treewidth may not be optimal for these algorithms. Instead of treewidth, we consider...
On Exact Algorithms for Treewidth (2006)
Hans Bodlaender Fedor, Hans L. Bodlaender, Fedor V. Fomin, Dieter Kratsch, Dimitrios M. Thilikos, ...
We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first...
Interval Routing and Minor-Monotone Graph (2006)
Parameters Erwin Bakker, Erwin M. Bakker, Hans L. Bodlaender, Richard B. Tan
We survey a number of minor-monotone graph parameters and their relationship to the complexity of routing on graphs. In particular we compare the interval routing parameters # slir (G) and # sir (G)...
Hans L. Bodlaender, Hans L. Bodlaender
This paper gives a short survey on algorithmic aspects of the treewidth of graphs. Some alternative characterizations and some applications of the notion are given. The paper also discusses...
Hans L. Bodlaender, Hans L. Bodlaender
The Feedback Vertex Set problem on unweighted, undirected graphs is considered.
Journal of Graph Algorithms and Applications (2006)
Http Jgaa Info, Treewidth Lower Bounds, Hans L. Bodlaender, Thomas Wolle
Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the...
Computation --- IWPEC 2006 (2006)
Hans Bodlaender Leizhen, Hans L. Bodlaender, Leizhen Cai, Jianer Chen, Michael R. Fellows, Jan Arne Telle, ...
In September 2006, the Second International Workshop on Parameterized and Exact Computation was held in Zurich, Switzerland, as part of ALGO 2006. At the end of IWPEC 2006, a problem session was...
Weighted treewidth: Algorithmic techniques and results (2006)
Emgad Bachoore, Emgad Bachoore, Hans L. Bodlaender, Hans L. Bodlaender
Abstract. From the analysis of algorithms for probabilistic networks, it is known that a tree decomposition of the minimum treewidth may not be optimal for these algorithms. Instead of treewidth, we...
Treewidth: Characterizations, applications, and computations (2006)
Hans L. Bodlaender, Hans L. Bodlaender
Abstract. This paper gives a short survey on algorithmic aspects of the treewidth of graphs. Some alternative characterizations and some applications of the notion are given. The paper also discusses...
A branch and bound algorithm for exact, upper, and lower bounds on treewidth (2006)
Emgad H. Bachoore, Emgad H. Bachoore, Hans L. Bodlaender, Hans L. Bodlaender
Abstract. In this paper, a branch and bound algorithm for computing the treewidth of a graph is presented. The method incorporates extensions of existing results, and uses new pruning and reduction...
Thilikos. On exact algorithms for treewidth (2006)
Hans L. Bodlaender, Fedor V. Fomin, Dieter Kratsch, Dieter Kratsch, Dimitrios M. Thilikos
We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first...
Treewidth: Characterizations, applications, and computations (2006)
Hans L. Bodlaender, Hans L. Bodlaender
Abstract. This paper gives a short survey on algorithmic aspects of the treewidth of graphs. Some alternative characterizations and some applications of the notion are given. The paper also discusses...
Treewidth: Characterizations, applications, and computations (2006)
Abstract. This paper gives a short survey on algorithmic aspects of the treewidth of graphs. Some alternative characterizations and some applications of the notion are given. The paper also discusses...
On the minimum corridor connection and other generalized geometric problems (2006)
Bodlaender, Hans L., Feremans, Corinne, Grigoriev, Alexander, Penninkx, Eelko, Sitters, Rene, Wolle, Thomas, ...
Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions (2005)
Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, V. Fomin
Abstract. A divide-and-conquer strategy based on variations of the Lipton-Tarjan planar separator theorem has been one of the most common approaches for solving planar graph problems for more than 20...
Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions (2005)
Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, Fedor V. Fomin
Abstract. Divide-and-conquer strategy based on variations of the LiptonTarjan planar separator theorem has been one of the most common approaches for solving planar graph problems for more than 20...
The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. This survey paper wants to give an overview of many classes of graphs that can be seen to have a uniform...
Hans L. Bodlaender, Hans L. Bodlaender, Hans L. Bodlaender, Joost Engelfriet, Joost Engelfriet, Joost Engelfriet
We consider a special variant of tree-decompositions, called domino treedecompositions, and the related notion of domino treewidth. In a domino tree-decomposition, each vertex of the graph belongs to...
Discovering Treewidth, Hans L. Bodlaender, Hans L. Bodlaender
Treewidth is a graph parameter with several interesting theoretical and practical applications. This survey reviews algorithmic results on determining the treewidth of a given graph, and finding a...
Tree Decompositions With Small Cost (2005)
Irit Katriel Hans, Irit Katriel, Hans L. Bodlaender, Hans L. Bodlaender
It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O(min{m log n}) time, an improvement over the best...
Algorithms for graphs embeddable with few crossings per edge (2005)
Alexander Grigoriev, Hans L. Bodlaender
www.cs.uu.nl Algorithms for graphs embeddable with few crossings per edge ∗
Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions (2005)
Hans L. Bod, Frederic Dorn, Frederic Dorn, Eelko Penninkx, Eelko Penninkx, Hans L. Bodlaender, ...
Abstract. A divide-and-conquer strategy based on variations of the Lipton-Tarjan planar separator theorem has been one of the most common approaches for solving planar graph problems for more than 20...
Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions (2005)
Hans L. Bodlaender, Frederic Dorn, Frederic Dorn, Eelko Penninkx, Eelko Penninkx, Hansl. Bodlaender, ...
Abstract. A divide-and-conquer strategy based on variations of the Lipton-Tarjan planar separator theorem has been one of the most common approaches for solving planar graph problems for more than 20...
Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions (2005)
Frederic Dorn, Frederic Dorn, Eelko Penninkx, Eelko Penninkx, Hans L. Bodlaender, Hans L. Bodlaender, ...
Abstract Divide-and-conquer strategy based on variations of the Lipton-Tarjan planar separator theorem has been one of the most common approaches for solving planar graph problems for more than 20...
Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions (2005)
Frederic Dorn, Frederic Dorn, Eelko Penninkx, Eelko Penninkx, Hans L. Bodlaender, Hans L. Bodlaender, ...
Abstract Divide-and-conquer strategy based on variations of the LiptonTarjan planar separator theorem has been one of the most common approaches for solving planar graph problems for more than 20...
Online Topological Ordering (2005)
Katriel, Irit, Bodlaender, Hans L.
It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting $m$ edges can be solved in $O(\min\{m^{3/2}\log n,m^{3/2}+n^2\log n\})$...
Safe separators for treewidth (2004)
www.cs.uu.nl Safe separators for treewidth #
Space-Efficient Construction Variants of Dynamic Programming (2004)
Hans L. Bodlaender, Jan Arne Telle
Many dynamic programming algorithms that solve a decision problem can be modified to one that solves the construction variant of the problem by additional bookkeeping and going backwards through...
Contraction Degeneracy on Cographs (2004)
Hans L. Bodlaender, Hans L. Bodlaender, Thomas Wolle, Thomas Wolle
The contraction degeneracy of a graph G is the maximum minimum degree of G # over all minors G # of G. The corresponding decision problem is known to be NP -complete.
With Few Crossings Per Edge (2004)
Alexander Grigoriev Hans, Hans L. Bodlaender
We consider graphs that can be embedded on a surface of bounded genus such that each edge has a bounded number of crossings. We prove that many optimization problems, including maximum independent...
Thomas Wolle, Arie Koster Hans, Hans L. Bodlaender, Thomas Wolle, Hans L. Bodlaender
The parameter contraction degeneracy --- the maximum minimum degree over all minors of a graph --- is a treewidth lower bound and was first defined in [3]. In experiments it was shown that this lower...
Thomas Wolle and Hans L. Bodlaender (2004)
Thomas Wolle, Hans L. Bodlaender, Thomas Wolle, Hans L. Bodlaender
Contracting an edge is the operation that introduces a new vertex that is adjacent to all vertices the endpoints of the contracted edge are adjacent to, and then deletes the endpoints of this edge...
Space-Ecient Construction Variants of (2004)
Dynamic Programming Hans, Hans L. Bodlaender, Jan Arne Telle
Many dynamic programming algorithms that solve a decision problem can be modified to one that solves the construction variant of the problem by additional bookkeeping and going backwards through...
Thomas Wolle Hans, Hans L. Bodlaender, Degree-based Treewidth, Lower Bounds, ...
Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower...
Contraction and Treewidth Lower Bounds (2004)
Hans Bodlaender Arie, Treewidth Lower Bounds, Hans L. Bodlaender, Thomas Wolle, Treewidth Lower Bounds
Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the...
Lower Bound for Treewidth (2004)
Hans Bodlaender Arie, Hans L. Bodlaender, Bound For Treewidth
The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An...
Contraction degeneracy on cographs (2004)
Hans L. Bodlaender, Hans L. Bodlaender, Thomas Wolle, Thomas Wolle
Abstract. The contraction degeneracy of a graph G is the maximum minimum degree of G ′ over all minors G ′ of G. The corresponding decision problem is known to be NP-complete. In this paper, we...
Safe separators for treewidth (2004)
www.cs.uu.nl Safe separators for treewidth ∗
Contraction and treewidth lower bounds (2004)
Hans L. Bodlaender, Thomas Wolle, Treewidth Lower Bounds
Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the...
On the Maximum Cardinality Search lower bound for treewidth (2004)
The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An...
Equitable Colorings of Bounded Treewidth Graphs (2004)
Hans L. Bodlaender, Fedor V. Fomin
A proper coloring of a graph G is equitable if the sizes of any two color classes are di#er by at most one. The related notion is #-bounded coloring where each of the color classes is of cardinality...
Approximations for {lambda}-Colorings of Graphs (2004)
Bodlaender, Hans L., Kloks, Ton, Tan, Richard B., Van Leeuwen, Jan
A λ-coloring of a graph G is an assignment of colors from the integer set {0,…,λ} to the vertices of the graph G such that vertices at distance of at most two get different colors and adjacent...
Rectilinear graphs and angular resolution (2003)
Hans L. Bodlaender, Gerard Tel
In this note we show that a planar graph with angular resolution at least #/2 can be drawn with all angles an integer multiple of #/2, that is, in a rectilinear manner. Moreover, we show that for d...
Hans L. Bodlaender, Hans L. Bodlaender, Thomas Wolle, Thomas Wolle
Abstract. Let be given an undirected, simple graph G = (V, E). We associate to each vertex a number in [0, 1]- its reliability, i.e. the probability that it does not fail. Furthermore, let a set S V...
Hans L. Bodlaender, Hans L. Bodlaender, Thomas Wolle, Thomas Wolle
Abstract. Let be given an undirected, simple graph G = (V, E). We associate to each vertex a number in [0, 1]- its reliability, i.e. the probability that it does not fail. Furthermore, let a set S...
Rectilinear graphs and angular resolution (2003)
Hans L. Bodlaender, Gerard Tel
In this note we show that a planar graph with angular resolution at least π/2 can be drawn with all angles an integer multiple of π/2, that is, in a rectilinear manner. Moreover, we show that for d...
problems. In Scandinavian Workshop on Algorithm Theory, pages 97–110, (2003)
Daniel M. Klein, Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier, Alewyn P. Burger, ...
A lottery is a game in which a person chooses n numbers from a universal set of m numbers to form a ticket, and where a winning ticket of t numbers is chosen and where the person wins if k or more of...
On Algorithms for (P_5,Gem)-Free Graphs (2003)
Hans L. Bodlaender, Andreas Brandstädt, Andreas Brandst Adt, Dieter Kratsch, Micha El Rao, ...
A graph is (P 5 ,gem)-free, when it does not contain P 5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the...
Partially supported by the Future and Emerging Technologies programme of the EU (2003)
Hans L. Bodlaender, Gerard Tel
We connect two aspects of graph drawing, namely angular resolution, and the possibility to draw with all angles an integer multiple of 2π/d. A planar graph with angular resolution at least π/2...
Tree decompositions with small cost (2002)
Hans L. Bodlaender, Hans L. Bodlaender, Fedor V. Fomin, Fedor V. Fomin
www.cs.uu.nl Tree decompositions with small cost
Derivation of algorithms for cutwidth and related graph layout problems (2002)
Hans L. Bodlaender, Hans L. Bodlaender, Michael R. Fellows, Michael R. Fellows, Dimitrios M. Thilikos, Dimitrios M. Thilikos
www.cs.uu.nl Derivation of algorithms for cutwidth and related graph layout parameters
Derivation of algorithms for cutwidth and related graph layout problems (2002)
Hans L. Bodlaender, Michael R. Fellows, Dimitrios M. Thilikos
In this paper, we investigate algorithms for some related graph parameters. Each of these asks for a linear ordering of the vertices of the graph (or can be formulated as such), and constructive...
Derivation of Algorithms for Cutwidth and Related Graph Layout Parameters (2002)
Hans L. Bodlaender, Michael R. Fellows, Dimitrios M. Thilikos
In this paper, we investigate algorithms for some related graph parameters. Each of these asks for a linear ordering of the vertices of the graph (or can be formulated as such), and constructive...
Gaag. Pre-processing for triangulation of probabilistic networks (2001)
Frank Van, Den Eijkhof, Linda C. Van, Der Gaag, Hans L. Bodlaender, ...
The currently most e#cient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding...
Treewidth: Computational experiments (2001)
Many NP-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown...
Reduction algorithms for graphs of small treewidth (2001)
Hans L. Bodlaender, Babette De Fluiter
This paper presents a number of new ideas and results on graph reduction applied to graphs of bounded treewidth. Arnborg et al. [2] have shown that many decision problems on graphs can be solved in...
Gaag. Preprocessing for triangulation of probabilistic networks (2001)
The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding...
Approximation of Pathwidth of Outerplanar Graphs (2001)
Hans L. Bodlaender, Fedor V. Fomin
There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs [3], but the large exponent makes this algorithm impractical. In this paper, we give an algorithm, that given a...
A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth (2001)
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
this paper, we move one step further presenting an polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth. The notions of treewidth and pathwidth appear to play a...
Reduction algorithms for graphs of small treewidth (2001)
Hans L. Bodlaender, Babette De Fluiter
This paper presents a number of new ideas and results on graph reduction applied to graphs of bounded treewidth. Arnborg et al. [2] have shown that many decision problems on graphs can be solved in...
On Game-Theoretic Models of Networks (2001)
Hans L. Bodlaender, Hans L. Bodlaender, Michaelj. Dinneen, Bakhadyr Khoussainov, Bakhadyr Khoussainov
Abstract. In this paper, we study the complexity of deciding which player has a winning strategy in certain types of McNaughton games. These graph games can be used as models for computational...
A constructive linear time algorithm for smal cutwidth (2000)
Thilikos, Dimitrios M., Serna, Maria J., Bodlaender, Hans L.
Constructive linear time algorithms for small cutwidth and carving-width (2000)
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
The cutwidth of a graph G is defined to be the smallest integer k such that the vertices of G can be arranged in a linear layout [v1,..., vn] in such a way that for every i = 1,..., n−1, there are...
Leeuwen. λ-Coloring of Graphs (2000)
Hans L. Bodlaender, Ton Kloks, Richard B. Tan
A λ-coloring of a graph G is an assignment of colors from the integer set {0,...,λ} to the vertices of the graph G such that vertices at distance of at most two get different colors and adjacent...
On the complexity of the Maximum Cut problem (2000)
Hans L. Bodlaender, Klaus Jansen
The complexity of the simple maxcut problem is investigated for several special classes of graphs. It is shown that this problem is NP-complete when restricted to one of the following classes:...
A Constructive Linear Time Algorithm for Small Cutwidth (2000)
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
this paper we show how to construct, for any constant k, a linear time algorithm that for any input graph
Approximations for lambda-Coloring of Graphs (2000)
Hans L. Bodlaender, Ton Kloks, Richard B. Tan, Jan Van Leeuwen
A #-coloring of a graph G is an assignment of colors from the integer set {0, . . . , #} to the vertices of the graph G such that vertices at distance at most two get di#erent colors and adjacent...
Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width (2000)
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
Consider the following problem: For any constant k and any input graph G, check whether there exists a tree T with internal vertices of degree 3 and a bijection mapping the vertices of G to the...
A Constructive Linear Time Algorithm for Small Cutwidth (2000)
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
this paper we show how to
Fixed Parameter Algorithms for Planar Dominating Set and Related Problems (2000)
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c # k n), where c = 3 6 # 34 . To obtain this result, we show that the...
Necessary Edges in K-Chordalizations of Graphs (2000)
In this note, we look at which edges must always be added to a given graph G = (V, E), when we want to make it a chordal graph with maximum clique size at most k by adding edges. lThis problem has a...
Fixed Parameter Algorithms for Planar Dominating Set and Related Problems (2000)
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c p k n), where c = 3 6 p 34 . To obtain this result, we show that the...
Approximation of Pathwidth of Outerplanar Graphs (2000)
Hans L. Bodlaender, Fedor V. Fomin
There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs [3], but the large exponent makes this algorithm impractical. In this paper, we give an algorithm, that given a...
Fixed parameter algorithms for planar dominating set and related problems (2000)
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c √ kn), where c = 36√34. To obtain this result, we show that the...
Constructive linear time algorithms for small cutwidth and carving-width (2000)
Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender
The cutwidth of a graph G is defined to be the smallest integer k such that the vertices of G can be arranged in a linear layout [v1,..., vn] in such a way that for every i = 1,..., n−1, there are...
Thilikos, Graphs with branchwidth at most three (1999)
Hans L. Bodlaender, Dimitrios M. Thilikos
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three, if and...
Sizes of decision tables and decision trees (1999)
Hans Zantema, Hans L. Bodlaender
Decision tables provide a natural framework for knowledge acquisition and representation in the area of knowledge based information systems. Decision trees provide a standard method for inductive...
A Note on Domino Treewidth (1999)
this paper seems unable to yield linear time algorithms - the approach typically leads to algorithmic results of
A Note on Domino Treewidth (1999)
this paper seems unable to yield linear time algorithms - the approach typically leads to algorithmic results of n log n) time. It is open whether domino tree decompositions of O(kd
A Note on Domino Treewidth (1999)
this paper seems unable to yield linear time algorithms - the approach typically leads to algorithmic results of n log n) time. It is open whether domino tree decompositions of O(kd
Thilikos, Graphs with branchwidth at most three (1999)
Hans L. Bodlaender, Dimitrios M. Thilikos
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three, if and...
A note on domino treewidth (1999)
In [DO95], Ding and Oporowski proved that for every k, and d, there exists a constant c k,d, such that every graph with treewidth at most k and maximum degree at most d has domino treewidth at most c...
Computing small search numbers in linear time (1998)
Hans L. Bodlaender, Dimitrios M. Thilikos
Let G = (V; E) be a graph. The linear-width of G is defined as the smallest integer k such that E can be arranged in a linear ordering (e 1; : : : ; e r) such that for every i = 1; : : : ; r \Gamma...
Computing small search numbers in linear time (1998)
Hans L. Bodlaender, Dimitrios M. Thilikos
Abstract. Let G = (V, E) be a graph. The linear-width of G is defined as the smallest integer k such that E can be arranged in a linear ordering (e1,..., er) such that for every i = 1,..., r−1,...
Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, ...
.<F3.814e+05> A vertex (edge) coloring<F3.687e+05> #<F3.814e+05> :<F3.687e+05> V<F5.57e+05> #<F3.814e+05><F3.687e+05> {1,<F3.814e+05><F3.687e+05>...
Treewidth and Minimum Fill-in on d-Trapezoid Graphs (1998)
Hans L. Bodlaender, Ton Kloks, Dieter Kratsch, Haiko Müller
We show that the minimum fill-in and the minimum interval graph completion of a d-trapezoid graph can be computed in time O(n d). We also show that the treewidth and the pathwidth of a d-trapezoid...
Computing small search numbers in linear time (1998)
Hans L. Bodlaender, Dimitrios M. Thilikos
Let G =(V;E) be a graph. The linear-width of G is de ned as the smallest integer k such that E can be arranged in a linear ordering (e1;:::;er) such that for every i =1;:::;r, 1, there are at most k...
Hans L. Bodlaender, Fedor V. Fomin
Equitable colorings of bounded treewidth
Comparing loop cutsets and clique trees in probabilistic networks (1997)
More and more knowledge-based systems are being developed that employ the framework of Bayesian belief networks for reasoning with uncertainty. Such systems generally use for probabilistic inference...
Treewidth: Algorithmic techniques and results (1997)
This paper gives an overview of several results and techniques for graphs algorithms that compute the treewidth of a graph or that solve otherwise intractable problems when restricted graphs with...
Parallel algorithms for series parallel graphs (1997)
Hans L. Bodlaender, Babette De Fluiter
In this paper, a parallel algorithm is given that, given a graph G = (V; E), decides whether G is a series parallel graph, and if so, builds a decomposition tree for G of series and parallel...
Parallel algorithms for series parallel graphs (1997)
Hans L. Bodlaender, Babette De Fluiter
In this paper, a parallel algorithm is given that, given a graph G = (V;E), decides whether G is a series parallel graph, and if so, builds a decomposition tree for G of series and parallel...
Constructive Linear Time Algorithms for Branchwidth (Extended Abstract) (1997)
Hans L. Bodlaender, Dimitrios M. Thilikos
) Hans L. Bodlaender Dimitrios M. Thilikos Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands E-mail: fhansb,sedthilkg@cs.ruu.nl Abstract Let G k be...
Constructive Linear Time Algorithms for Branchwidth (1997)
Dimitrios M. Thilikos, Hans L. Bodlaender
We prove that, for any fixed k, one can construct a linear time algorithm that checks if a graph has branchwidth# k and, if so, outputs a branch decomposition of minimum width. 1
Graphs with Branchwidth at most Three (1997)
Hans L. Bodlaender, Dimitrios M. Thilikos
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and...
Isomorphism for Graphs of Bounded Distance Width (1997)
Koichi Yamazaki, Hans L. Bodlaender, Babette De Fluiter, Dimitrios M. Thilikos
In this paper, we study the Graph Isomorphism problem on graphs of bounded treewidth, bounded degree or bounded bandwidth. Graph Isomorphism can be solved in polynomial time for graphs of bounded...
Parallel algorithms for series parallel graphs (1997)
Hans L. Bodlaender, Babette De Fluiter
In this paper, a parallel algorithm is given that, given a graph G =(V;E), decides whether G is a series parallel graph, and if so, builds a decomposition tree for G of series and parallel...
Comparing loop cutsets and clique trees in probabilistic networks (1997)
More and more knowledge-based systems are being developed that employ the framework of Bayesian belief networks for reasoning with uncertainty. Such systems generally use for probabilistic inference...
Dimitrios M. Thilikos, Hans L. Bodlaender
A graph is l-apex if it can be made planar by removing at most l vertices. In this paper we show that the vertex set of any graph not containing an lapex graph as a minor can be quickly partitioned...
It is hard to know when greedy is good for finding independent sets (1997)
Hans L. Bodlaender, Dimitrios M. Thilikos, Koichi Yamazaki
The classesAr andSr are de ned as the classes of those graphs, where the minimum degree greedy algorithm always approximates the maximum independent set (MIS) problem within a factor of r,...
Parallel algorithms for series parallel graphs (1997)
Hans L. Bodlaender, Babette De Fluiter
In this paper, a parallel algorithm is given that, given a graph G = (V; E), decides whether G is a series parallel graph, and if so, builds a decomposition tree for G of series and parallel...
On intervalizing k-colored graphs for DNA physical mapping (1996)
Hans L. Bodlaender, Babette De Fluiter
The problem to determine whether a given k-colored graph is a subgraph of a properly colored interval graph has an application in DNA physical mapping. In this paper, we study the problem for the...
Restrictions of graph partition problems (1995)
Part I, Hans L. Bodlaender, Hans L. Bodlaender, Klaus Jansen, Klaus Jansen, Klaus Jansen T
of graph partition
Parallel algorithms with optimal speedup for bounded treewidth (1995)
Hans L. Bodlaender, Torben Hagerup
We describe the first parallel algorithm with optimal speedup for constructing minimum-width tree decompositions of graphs of bounded treewidth. On n-vertex input graphs, the algorithm works in...
minimum elimination tree height (1995)
Hans L. Bodlaender, Hans L. Bodlaender, John R. Gilbert, John R. Gilbert, Hjlmtr Hafsteinsson, Hjlmtr Hafsteinsson, ...
We show how the value of various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex...
On Interval Routing Schemes and Treewidth (1995)
Hans L. Bodlaender, Richard B. Tan, Dimitrios M. Thilikos, Jan Van Leeuwen
. In this paper, we investigate which processor networks allow k- label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixed k # 1, the class of...
The parameterized complexity of sequence alignment and consensus (1995)
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows
The Longest common subsequence problem is examined from the point of view of parameterized computational complexity. There are several di erent ways in which parameters enter the problem, such as the...
Hans L. Bodlaender, Hans L. Bodlaender, Hans L. Bodlaender
It is shown, that for each constant k _ 1, the following problems can be solved in O(n) time: given a graph G, determine whether G has k vertex disjoint cycles, determine whether G has k edge...
W[2]-hardness of precedence constrained k-processor scheduling (1994)
Hans L. Bodlaender, Michael R. Fellows
It is shown that the Precedence Constrained K-Processor Scheduling problem is W [2]-hard. This means that there does not exist a constant c, such that for all fixed K, the Precedence Constrained...
On reduction algorithms for graphs with small treewidth (1994)
Hans L. Bodlaender, Babette De Fluiter
This paper presents some new ideas and results on graph reduction applied to graphs with bounded treewidth. Arnborg et al. [2] have shown that many decision problems on graphs can be solved in linear...
Trade-offs in non-reversing diameter (1994)
Hans L. Bodlaender, Nicola Santoro
Consider a tree T with a number of extra edges (the bridges) added. We consider the notion of diameter, that is obtained by admitting only paths p with the property that for every bridge b in path p,...
Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett
The parameterized computational complexity of a collection of well-known problems including: Bandwidth, Precedence constrained k-processor scheduling, Longest Common Subsequence, DNA physical mapping...
Dynamic Algorithms for Graphs with Treewidth 2 (1994)
In this paper, we consider algorithms for maintaining treedecompositions with constant bounded treewidth under edge and vertex insertions and deletions for graphs with treewidth at most 2 (also...
Kayles on special classes of graphs --- An application of Sprague-Grundy theory (1993)
Kayles is the game, where two players alternately choose a vertex that has not been chosen before nor is adjacent to an already chosen vertex from a given graph. The last player that choses a vertex...
A tourist guide through treewidth (1993)
A short overview is given of many recent results in algorithmic graph theory that deal with the notions treewidth, and pathwidth. We discuss algorithms that find tree-decompositions, algorithms that...
The pathwidth and treewidth of cographs (1993)
Rolf H. Mshring, Hans L. Bodlaender, Hans L. Bodlaender, Rolf H. M/shring
The pathwidth and treewidth of a graph are two notions with a large number of different applications in many areas, like algorithmic graph theory, VLSI-design and others (see e.g. [1, 13])....
Kayles on special classes of graphs --- An application of Sprague-Grundy theory (1993)
Kayles is the game, where two players alternately choose a vertex that has not been chosen before nor is adjacent to an already chosen vertex from a given graph. The last player that choses a vertex...
In this paper we give, for all constants k, l, explicit algorithms that, given a graph G�Ž V, E. with a tree-decomposition of G with treewidth at most l, decide whether the treewidth Ž or...
Two Strikes Against Perfect Phylogeny (1992)
Hans L. Bodlaender, Hans L. Bodlaender, Mike R. Fellows, Y J. Wamow, Y J. Warnow, ...
One of the major efforts in molecular biology is the computation of phylo-genies for species sets. A longstanding open problem in this area is called the Perfect Phylogeny problem. For almost two...
On the complexity of some coloring games (1991)
Hans L. Bodlaender, Hans L. Bodlaender
In this paper we consider the following game: players must alter-nately color the lowest numbered uncolored vertex of a given graph G = ({1, 2,-.., n), E) with a color, taken from a given set C, such...
Planar graph augmentation problems (1991)
P. O. Bex, Goos Kant, Goos Kant, Hans L. Bodlaender, Hans L. Bodlaender
Instance: Connected, planar graph G = (V, E). Question: Find a planar, biconnected graph H = (V, F) with E C _ F, and IF- E I as small as possible. Eswaran & Tarjan [2] studied this augmentation...
Several new lower bounds are derived for deterministic and randomized extrema finding and some other problems on asynchronous, non-anonymous rings of processors, where the ring size n is known in...
Restrictions of graph partition problems, part i (1991)
Hans L. Bodlaender, Klaus Jansen
In this paper partition problems into k independent sets or cliques of bounded size k 0 are analysed for several classes of graphs. We prove the computational complexity of both problems restricted...
The maximum cut and minimum cut into bounded sets problems of cographs, manuscript (1987)
Hans L. Bodlaender, Hans L. Bodlaender, Hans Bodlaender
In this note we give simple O(n 2) algorithms for the unweighted MAX CUT problem and the unweighted MINIMUM CUT INTO BOUND-.D S.TS problem on cographs. The algorithms can easily be modified such that...
Treewidth: Computational Experiments.
Many NP-complete graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have...