References References for L(2, 1)-labelings (2008)
Gerard Jennhwa Chang, H. L. Bodlaender, T. Kloks, R. B. Tan, J. Van Leeuwen, A. A. Bertossi, ...
[2] H. L. Bodlaender, T. Kloks, R. B. Tan, and J. van Leeuwen, Approximations for λ-colorings of graphs, Computer J. (to appear).
Finding and Counting Small Induced Subgraphs Efficiently (2007)
T. Kloks, D. Kratsch, H. Müller
We give two algorithms for listing all simplicial vertices of a graph. The first of these algorithms takes O(n ff ) time, where n is the number of vertices in the graph and O(n ff ) is the time...
Ton Kloks, T. Kloks, Haiko Müller, Dieter Kratsch, H. Muller
. A graph is called a domino if every vertex is contained in at most two maximal cliques. The class of dominoes properly contains the class of line graphs of bipartite graphs, and is in turn properly...
Pathwidth Of, Pathwidth Of, T. Kloks, T. Kloks, T. Kloks, H. Bodlaender, ...
In this paper we discuss the problem of finding the treewidth and pathwidth of permutation graphs. If G[r] is a permutation graph with treewidth k, then we show that the pathwidth of G[r] is at most...
Fast Algorithms for the TRON Game on Trees (2007)
T. Kloks, T. Kloks, H. Bodlaender, H. Bodlaender, H. Bodlaender, T. Klokst
TION is the following game which can be played on any graph: Two players choose lternately a node of the graph subject to the requirement that each player must choose a node which is adjacent to his...
Testing superperfection of k-trees (2007)
T. Kloks, T. Kloks, T. Kloks, H. Bodlaender, H. Bodlaender, H. Bodlaender
An interval coloring of a weighted graph with non-negative weights, maps each vertex onto an open interval on the real line with width equal to the weight of the vertex, such that adjacent vertices...
H. Bodlaender, H. Bodlaender, H. Bodlaender, T. Gonzalez, T. Gonzalez, T. Gonzalez, ...
Complexity aspects of 2-dimensional data compression
H. L. Bodlaender, J. S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Muller
A vertex (edge) coloring c: V! f1; 2; : : : ; tg (c 0: E! f1; 2; : : : ; tg) of a graph G = (V; E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between...
Kernels in planar digraphs (2005)
Gutin, G., Kloks, T., Lee, C.M., Yeo, A.
A set S of vertices in a digraph D=(V,A) is a kernel if S is independent and every vertex in V-S has an out-neighbor in S. We show that there exist -time and -time algorithms for checking whether a...
Kernels in planar digraphs (2005)
Gutin, G., Kloks, T., Lee, C.M., Yeo, A.
A set S of vertices in a digraph D=(V,A) is a kernel if S is independent and every vertex in V-S has an out-neighbor in S. We show that there exist -time and -time algorithms for checking whether a...
Kernels in planar digraphs (2005)
Gutin, G., Kloks, T., Lee, C.M., Yeo, A.
A set S of vertices in a digraph D=(V,A) is a kernel if S is independent and every vertex in V-S has an out-neighbor in S. We show that there exist -time and -time algorithms for checking whether a...
A generalization of AT-free graphs and a generic algorithm for solving triangulation problems (2002)
Degree-preserving forests (2000)
Broersma, H.J., Huck, A., Kloks, T., Koppius, O., Muller, H.C., Tuinstra, H.
A generalization of AT-free graphs and a generic algorithm for solving triangulation problems (1998)
Degree-preserving forests (1998)
Broersma, H.J., Huck, A., Kloks, T., Koppius, O., Kratsch, D., Muller, H.C., ...
Degree-preserving forests (1998)
Broersma, H.J., Huck, A., Kloks, T., Koppius, O., Kratsch, D., Muller, H.C., ...
A generalization of AT-free graphs and a generic algorithm for solving triangulation problems (1998)
Listing All Minimal Separators of a Graph (1998)
An effcient algorithm listing all minimal vertex separators of an undirected graph is given. The algorithm needs polynomial time per separator that is found.
Listing All Minimal Separators of a Graph (1998)
. An efficient algorithm listing all minimal vertex separators of an undirected graph is given. The algorithm needs polynomial time per separator that is found. 1 Introduction Given a graph, one is...
H. L. Bodlaender, J. S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, ...
A vertex (edge) coloring c: V!f1; 2;:::;tg (c 0: E!f1; 2;:::; tg) of a graph G =(V;E) isavertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a...
Efficient and constructive algorithms for the pathwidth and treewidth of graphs (1996)
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)...
Minimum Fill-in on Circle and Circular-Arc Graphs (1996)
T. Kloks, D. Kratsch, C. K. Wong
. We present two algorithms solving the minimum fill-in problem on circle graphs and on circular-arc graphs in time O(n 3 ). 1 Introduction The minimum fill-in problem is a well known and often...
Treewidth of chordal bipartite graphs (1995)
D. Kratsch, D. Kratsch, T. Kloks, T. Kloks, T. Kloks
Chordal bipartite graph are exactly those bipartite graph in which every cycle of length at least six has a chord. The treewidth of a graph G is the smallest maximum cliquesize among all chordal...
Computing the Toughness and the Scattering Number for Interval and Other Graphs (1994)
H. Müller, D. Kratsch, D. Kratsch, T. Kloks, T. Kloks, H. Muller
: We show that the scattering number and the toughness of a graph, two graph parameters strongly related to hamiltonian properties of graphs, can be computed in polynomial time on interval graphs,...
Computing the Toughness and the Scattering Number for Interval and Other Graphs (1994)
D. Kratsch, T. Kloks, H. Müller
: We show that the scattering number and the toughness of a graph, two graph parameters strongly related to hamiltonian properties of graphs, can be computed in polynomial time on interval graphs,...
Efficient and constructive algorithms for the pathwidth and treewidth of graphs (1993)
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)...
Only few graphs have bounded treewidth (1992)
H. Bodlaender, H. Bodlaender, T. Kloks, T. Kloks, T. Kloks, H. Bodlaendert
few graphs have bounded treewidth