Dimitrios M. Thilikos

Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos

We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this...

Subexponential (2008)

parameterized algorithms

Algorithmica manuscript No. (will be inserted by the editor) Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors ⋆ (2008)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

The date of receipt and acceptance will be inserted by the editor Abstract We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs...

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...

On (2008)

Hans L. Bodlaender, Fedor V. Fomin, Dieter Kratsch, Dimitrios M. Thilikos

www.cs.uu.nl

AND (2008)

Erik D. Demaine, Dimitrios M. Thilikos

Abstract. We introduce a new framework for designing fixed-parameter algorithms with subexponential running time—2 O( √ k) n O(1). Our results apply to a broad family of graph problems, called...

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...

Fast FPT-algorithms (2008)

Josep Díaz, Dimitrios M. Thilikos

for cleaning grids ∗

Algorithmica manuscript No. (will be inserted by the editor) Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors ⋆ (2008)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

The date of receipt and acceptance will be inserted by the editor Abstract We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs...

and (2008)

Erik D. Demaine, Dimitrios M. Thilikos

A preliminary version of this article appeared in the Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP’03). F. Fomin is supported by Norges...

Fast approximation schemes for K_{3,3}-minor-free or K_5-minor-free graphs (2008)

Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

We prove that any graph excluding one of K5 or K3;3 as a minor has local treewidth bounded by 3k + 4. As a result, we can design practical polynomial-time approximation schemes for both minimization...

Efficient algorithms for counting parameterized list H-Colorings (2008)

We study the fixed parameter tractability of the counting version of a parameterization of the restrictive list H-coloring problem. The parameterization is defined by fixing the number of preimages...

yz (2007)

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

The problem of counting all H-colorings of a graph G of n vertices is considered. While the problem is, in general, #P-complete, we give linear time algorithms that solve the main variants of this...

Isomorphism for Graphs of Bounded Distance Width (2007)

The problem of counting all H-colorings of a graph G of n vertices is considered. While the problem is, in general, #P-complete, we give linear time algorithms that solve the main variants of this...

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...

Quickly Excluding (2007)

From Planar Graphs, Dimitrios M. Thilikos, Dimitrios M. Thilikos

We prove that any planar graph that does not contain K 2;r as a minor has treewidth r + 2. 3 1 introduction In this paper we consider finite graphs without loops or multiple edges. We will denote the...

Quickly Excluding K 2,r from Planar Graphs (2007)

excluding single-crossing graphs as minors (2007)

We prove that any planar graph that does not contain K 2;r as a minor has treewidth r + 2. 1 introduction In this paper we consider finite graphs without loops or multiple edges. We will denote the...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Prabhakar Ragde, Dimitrios M. Thilikos

algorithms for classes of graphs

and Theoretical Computer Science Recent results on Parameterized H-Coloring (2007)

H-colorings of Large Degree Graphs (2007)

Abstract. We survey recent results on the complexity of several versions of the H-coloring and the list-H-coloring problems that are amenable to parameterization. 1.

We consider the H-coloring problem on graphs with vertices of large degree. We prove that for H an odd cycle, the problem belongs to P. We also study the phase transition of the problem, for an...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

graphs as minors

Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs (2007)

We dene a variant of the H-coloring problem where the number of preimages of certain vertices is predetermined as part of the problem input. We consider the decision and the counting version of the...

We introduce a new framework for designing fixed-parameter algorithms with subexponential running time—2 O( √ k) n O(1). Our results apply to a broad family of graph problems, called...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. We present a fixed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K5 or K3;3 as a minor in time O(3 6

DIMACS Series in Discrete Mathematics and Theoretical Computer Science Recent results on Parameterized H-Coloring (2007)

Jaroslav Nesetril, Maria Serna, Dimitrios M. Thilikos

Abstract. We survey recent results on the complexity of several versions of the H-coloring and the list-H-coloring problems that are amenable to parameterization.

, and (2007)

Abstract. We consider the H-coloring problem on graphs with vertices of large degree. We prove that for H an odd cycle, the problem belongs to P. We also study the phase transition of the problem,...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. We present a xed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K5 or K3;3 as a minor in time O(3 6

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...

Contiguous and Internal Graph Searching (2007)

Pierre Fraigniaud, Nicola Santoro, Dimitrios M. Thilikos

Graph searching refers to a problem that has been throughly and extensively investigated in the literature, and that describes a variety of application scenarios ranging from \decontaminating a set...

graphs with Applications to Approximating Maximum Induced-Subgraph Problems (2007)

l-apex

Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

graphs

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender

We study the counting versions of several variants of the H-coloring problem. The complexity of the #H-coloring problem is described by a dichotomy theorem that classies the problem according to the...

cutwidth and (2007)

Constructive linear time algorithms for small

cutwidth and (2007)

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender

Constructive linear time algorithms for small

and (2007)

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender

polynomial time algorithm for the cutwidth of bounded degree graphs

generalizations of (2007)

We study the counting versions of several variants of the H-coloring problem. The complexity of the #H-coloring problem is described by a dichotomy theorem that classies the problem according to the...

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

xed-parameter tractable algorithms for nontrivial

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

of vertex cover

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender

The problem of counting all H-colorings of a graph G of n vertices is considered. While the problem is, in general, #P-complete, we give linear time algorithms that solve the main variants of this...

and (2007)

polynomial time algorithm for the cutwidth of bounded degree graphs

Quickly Excluding K_2,r From Planar Graphs (2007)

Dimitrios M. Thilikos, Dimitrios M. Thilikos

We prove that any planar graph that does not contain K 2,r as a minor has treewidth r + 2. 1 introduction In this paper we consider finite graphs without loops or multiple edges. We will denote the...

The Price of Connectedness in Expansions (2007)

Fedor Fomin, Pierre Fraigniaud, Dimitrios M. Thilikos, Lenguatges I Sistemes

Expansion is the way of generalizing di#erent graph layout and searching problems. We initiate the study of connected expansion which naturally arises in a number of applications.

Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2007)

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos

The (k, r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k,...

generalizations of vertex cover (2007)

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

fixed-parameter tractable algorithms for nontrivial

Monotonicity and Inert Fugitive Search (2007)

Yannis C. Stamatiou, Dimitrios M. Thilikos

In general, graph search can be described in terms of a sequence of searchers ’ moves on a graph, able to capture a fugitive resorting on its vertices/edges. Several variations of graph search have...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

graphs as minors

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

For several graph theoretic parameters such as vertex cover and dominating set, it is known that if their values are bounded by k then the treewidth of the graph is bounded by some function of k....

Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs ∗ (2007)

Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-up (2007)

The (k, r)-center problem asks whether an input graph G has ≤ k vertices (called centers) such that every vertex of G is within distance ≤ r from some center. In this paper we prove that the (k,...

Subexponential parameterized algorithms (2007)

Preprocessing by data reduction is a simple but powerful technique used for practically solving di#erent network problems. A number of empirical studies shows that a set of reduction rules for...

Abstract (2007)

Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos, B Er, G E Nsis, Frederic Dorn, ...

We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex Hminor-free graph G contains a path of length k in 2 O( √ k) · n O(1) steps. Our approach builds on a...

Subexponential Parameterized Algorithms, Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos, Frederic Dorn, Fedor V. Fomin, ...

Abstract We present a series of techniques for the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a...

(2 × ∞)-grid (2007)

Josep Díaz, Marcin Kamiński, Josep Díaz, Marcin Kamiński, Dimitrios M. Thilikos

R u t c o r

An annotated bibliography on guaranteed graph (2007)

On Exact Algorithms for Treewidth (2006)

searching

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...

Efficient algorithms for parameterized H-coloring (2006)

REPORTS IN INFORMATICS (2006)

Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos, Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos

Fast subexponential algorithm for non-local problems on graphs of bounded genus

On Self Duality of Pathwidth in Polyhedral Graph (2006)

Graph Embeddings, Fedor V. Fomin, Dimitrios M. Thilikos

Let G be a 3-connected planar graph and G ∗ be its dual. We show that the pathwidth of G ∗ is at most 6 times the pathwidth of G. We prove this result by relating the pathwidth of a graph with...

Parameterized complexity of finding regular induced subgraphs (2006)

Hannes Moser, Dimitrios M. Thilikos

abstract. The r-Regular Induced Subgraph problem asks, given a graph G and a non-negative integer k, whether G contains an r-regular induced subgraph of size at least k, that is, an induced subgraph...

Parameterized complexity of finding regular induced subgraphs (2006)

Hannes Moser, Dimitrios M. Thilikos

abstract. The r-Regular Induced Subgraph problem asks, given a graph G and a non-negative integer k, whether G contains an r-regular induced subgraph of size at least k, that is, an induced subgraph...

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...

Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors (2005)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K5 or K3;3 as a minor in time O(416:5 pk nO(1)), which is an...

The restrictive H-coloring problem (2005)

Josep Daz Maria, Maria Serna, Dimitrios M. Thilikos

We define a variant of the H-coloring problem where the number of preimages of certain vertices is predetermined as part of the problem input. We consider the decision and the counting version of the...

Bidimensional parameters and local treewidth (2004)

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. For several graph theoretic parameters such as vertex cover and dominating set, it is known that if their values are bounded by k then the treewidth of the graph is bounded by some function...

Bidimensional parameters and local treewidth (2004)

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k then the treewidth of the graph is bounded by some function...

The bidimensional theory of bounded-genus graphs (2004)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

1 Introduction The recent theory of fixed-parameter algorithms and parameterized complex-ity [13] has attracted much attention in its less than 10 years of existence. In general the goal is to...

The bidimensional theory of bounded-genus graphs (2004)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. Bidimensionality provides a tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper extends...

Bidimensional parameters and local treewidth (2004)

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

The bidimensional theory of bounded-genus graphs (2004)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. Bidimensionality is a powerful tool for developing subexponential fixedparameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper...

Recent results on parameterized H-colorings (2004)

Bidimensional Parameters and Local Treewidth (2004)

We survey recent results on the complexity of several versions of the H-coloring and the list-H-coloring problems that are amenable to parameterization.

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k then the treewidth of the graph is bounded by some function of k. This...

Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs (2004)

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos

We introduce a new framework for designing xed-parameter algorithms with subexponential running time|2 . Our results apply to a broad family of graph problems, called bidimensional problems, which...

Fixed parameter algorithms for counting and deciding bounded restrictive list H-colorings (2004)

The bidimensional theory of bounded-genus graphs (2004)

We are interested in studying the fixed parameter tractability of the counting and the decision version of a parameterization of the H-coloring problem. These problems are dened by xing a partial...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. Bidimensionality provides a tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper extends...

Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up (2004)

Fedor V. Fomin, Fedor V. Fomin, Dimitrios M. Thilikos, Dimitrios M. Thilikos

Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up

Bidimensional parameters and local treewidth (2004)

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, M. Thilikos, Dimitrios M. Thilikos

For several graph theoretic parameters such as vertex cover and dominating set, it is known that if their values are bounded by k then the treewidth of the graph is bounded by some function of k....

The price of connectedness in expansions (2004)

Fedor V. Fomin, Pierre Fraigniaud, Dimitrios M. Thilikos

Expansion is the way of generalizing different graph layout and searching problems. We initiate the study of connected expansion which naturally arises in a number of applications. Our main tool for...

Faster fixed-parameter tractable algorithms for matching and packing problems (2004)

Michael R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, ...

Abstract. We obtain faster algorithms for problems such as rdimensional matching, r-set packing, graph packing, and graph edge packing when the size k of the solution is considered a parameter. We...

Thilikos, Fixed-parameter algorithms for the (k, r)-center in planar graphs and map graphs (2003)

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2003)

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos

The (k, r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k,...

Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2003)

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos

Dominating sets in planar graphs: branch-width and exponential speed-up (2003)

On the monotonicity of games generated by symmetric submodular functions (2003)

Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory...

Dominating sets in planar graphs: branch-width and exponential speed-up (2003)

zx Submodular functions have appeared to be a key tool for proving the monotonicity of several graph searching games. In this paper we provide a general game theoretic framework able to unify old and...

New Upper Bounds on the Decomposability of Planar Graphs and Fixed Parameter Algorithms (2003)

Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory...

Fedor V. Fomin, Fedor V. Fomin, Dimitrios M. Thilikos, Dimitrios M. Thilikos

It is known that a planar graph on n vertices has branch-width/tree-width bounded by # # n.

REPORTS IN INFORMATICS (2003)

In Informatics Issn, Fedor V. Fomin, Fedor V. Fomin, Dimitrios M. Thilikos, Dimitrios M. Thilikos

It is known that a planar graph on n vertices has branch-width/tree-width bounded by # # n.

Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up (2003)

Fedor V. Fomin, Fedor V. Fomin, Dimitrios M. Thilikos, Dimitrios M. Thilikos

Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory...

Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up (2003)

Fedor V. Fomin, Fedor V. Fomin, Dimitrios M. Thilikos, Dimitrios M. Thilikos

Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory...

REPORTS IN INFORMATICS (2003)

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs

Fixed-parameter algorithms for the (k, r)-center in planar graphs and map graphs (2003)

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos

The (k; r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k;...

Connected and Internal Graph Searching (2003)

Lali Barriere, Pierre Fraigniaud, Nicola Santoro, Dimitrios M. Thilikos

This paper is concerned with the graph searching game. The search number s(G) of a graph G is the smallest number of searchers required to "clear" G. A search strategy is monotone (m) if no...

Thilikos, Fixed-parameter algorithms for the (k, r)-center in planar graphs and map graphs (2003)

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. The (k, r)-center problem asks whether an input graph G has ≤ k vertices (called centers) such that every vertex of G is within distance ≤ r from some center. In this paper we prove...

A 1.5-approximation for treewidth of graphs excluding a graph with one crossing (2002)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The...

A 1.5-approximation for treewidth of graphs excluding a graph with one crossing (2002)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The...

Exponential speedup of fixed-parameter algorithms on K_3,3-minor-free or K_5-minor-free graphs (2002)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at...

Exponential speedup of fixed parameter algorithms on K_3,3-minor-free or K_5-minor-free graphs (2002)

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

We present a fixed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K5 or K3,3 as a minor in time O(3 6 √ 34k n O(1)). In fact, we present...

The complexity of restrictive H-coloring (2002)

Thilikos, Exponential speedup of fixed parameter algorithms on K3,3-minor-free or K5-minor-free graphs (2002)

We define a variant of the H-coloring problem where the number of preimages of certain vertices is predetermined as part of the problem input. We consider the decision and the counting version of the...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. We present a fixed parameter algorithm that constructively solves the k-dominating set prob-lem on graphs excluding one of K5 or K3,3 as a minor in time O(36n()), which is an exponential...

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...

Thilikos, New upper bounds on the decomposability of planar graphs and fixed parameter algorithms, technical report, Universitat Politècnica de Catalunya (2002)

Exponential Speedup of Fixed Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors (2002)

fixed parameter algorithms

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

We present a fixed parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph (can be drawn on the plane with at most one...

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...

New Upper Bounds on the Decomposability of Planar Graphs and Fixed Parameter Algorithms (2002)

Thilikos. Exponential speedup of fixed-parameter algorithms on K3,3-minor-free or K5-minor-free graphs (2002)

It is known that a planar graph on n vertices has branch-width/tree-width bounded by # # n. In many algorithmic applications it is useful to have a small bound on the constant #. We give a proof of...

Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Abstract. We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K5 or K3,3 as a minor in time O(4 16.5 √ k n O(1)), which is an...

(H, C, K)-colorings: Fast, easy and hard cases (2001)

Josep Diaz, Maria Serna, Dimitrios M. Thilikos

We define a variant of the H-coloring problem by fixing the number of preimages of a subset C of the vertices of H, thus allowing parameterization. We provide sufficient conditions to guarantee that...

(H, C, K)-colorings: Fast, easy and hard cases (2001)

H, C, K)-Coloring: Fast, Easy, and Hard Cases (2001)

We define a variant of the H-coloring problem by fixing the number of preimages of a subset C of the vertices of H, thus allowing parameterization. We provide sufficient conditions to guarantee that...

Josep Daz Maria, Maria Serna, Dimitrios M. Thilikos

We define a variant of the H-coloring problem by fixing the number of preimages of a subset C of the vertices of H, thus allowing parameterization. We provide su#cient conditions to guarantee that...

Counting List H-Colorings and Variants (2001)

Josep Daz Maria, Maria Serna, Dimitrios M. Thilikos

We study the counting versions of several variants of the H-coloring problem.

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...

Fast Fixed-Parameter Tractable Algorithms for Nontrivial Generalizations of Vertex Cover (2001)

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size...

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...

Algorithms and obstructions for linear-width and related search parameters (2000)

Algorithms and Obstructions for Linear-Width and Related Search Parameters (2000)

The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering (e 1; : : : ; e r) in such a way that for every i = 1; : : : ; r...

A Constructive Linear Time Algorithm for Small Cutwidth (2000)

The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering (e 1 ; : : : ; e r ) in such a way that for every i = 1; : : : ; r...

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

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

On Graph Powers For Leaf-Labeled Trees (2000)

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

this paper are derived from two abundant areas of research: graph powers and leaflabeled trees. Both areas contain results of a purely theoretical nature as well as applications to such diverse areas...

H-colorings of Large Degree Graphs (2000)

Josep Daz Jaroslav, Josep Díaz, Maria Serna, Dimitrios M. Thilikos

We consider the H-coloring problem on graphs with vertices of large degree. We prove that for H an odd cycle, the problem belongs to P.

On Graph Powers for Leaf-Labeled Trees (2000)

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

. We extend the well-studied concept of a graph power to that of a k-leaf power G of a tree T : G is formed by creating a node for each leaf in the tree and an edge between a pair of nodes if and...

Finding Smallest Supertrees Under Minor Containment (2000)

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

The diversity of application areas relying on tree-structured data results in a wide interest in algorithms which determine differences or similarities among trees. One way of measuring the...

On Graph Powers for Leaf-Labeled Trees (2000)

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

this paper are derived from two abundant areas of research: graph powers and leaflabeled trees. Both areas contain results of a purely theoretical nature as well as applications to such diverse areas...

Finding Smallest Supertrees Under Minor Containment (2000)

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

The diversity of application areas relying on tree-structured data results in wide interest in algorithms which determine dierences or similarities among trees. One way of measuring the similarity...

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)

Monotonicity and Inert Fugitive Search Games (1999)

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...

Yannis Stamatiou School, Yannis C. Stamatiou, Dimitrios M. Thilikos

In general, graph search can be described in terms of a sequence of searchers' moves on a graph, able to capture a fugitive resorting on its vertices/edges. Several variations of graph search...

Finding Smallest Supertrees under Minor Containment (1999)

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

The diversity of application areas relying on tree-structured data results in a wide interest in algorithms which determine differences or similarities among trees. One way of measuring the...

Monotonicity and Inert Fugitive Search Games (1999)

Yannis C. Stamatiou, Dimitrios M. Thilikos

In general, graph search can be described in terms of a sequence of searchers' moves on a graph, able to capture a fugitive resorting on its vertices/edges. Several variations of graph search...

Monotonicity and Inert Fugitive Search Games (1999)

Yannis C. Stamatiou, Dimitrios M. Thilikos

In general, graph search can be described in terms of a sequence of searchers' moves on a graph, able to capture a fugitive resorting on its vertices/edges. Several variations of graph search...

Thilikos, Graphs with branchwidth at most three (1999)

Computing small search numbers in linear time (1998)

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...

Bodlaender, Hans L., Thilikos, Dimitrios M.

Computing small search numbers in linear time (1998)

Computing small search numbers in linear time (1998)

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)

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,...

Fugitive-search games on graphs and related parameters (1997)

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...

Nick D. Dendris, Lefieris M. Kirousis, Dimitrios M. Thilikos

Constructive Linear Time Algorithms for Branchwidth (Extended Abstract) (1997)

Constructive Linear Time Algorithms for Branchwidth (1997)

) 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...

It is Hard to Know when Greedy is Good for Finding Independent Sets (1997)

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

Hans Bodlaender Dimitrios, Dimitrios M. Thilikos, Koichi Yamazaki

The classes A r and S r are defined 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,...

It is Hard to Know when Greedy is Good for Finding Independent Sets (1997)

Hans Bodlaender, Dimitrios M. Thilikos, Koichi Yamazaki

The classes A r and S r are defined 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,...

Graphs with Branchwidth at most Three (1997)

Isomorphism for Graphs of Bounded Distance Width (1997)

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...

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...

Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems (1997)