Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width

Autor: Broersma, Haitze J., Golovach, Petr A., Patel, Viresh, Marx, Dániel, Rossmanith, Peter

Publikováno v: Parameterized and Exact Computation ISBN: 9783642280498
IPEC
Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, 207-218
STARTPAGE=207;ENDPAGE=218;TITLE=Parameterized and Exact Computation

We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::219646f9dc4004ea8cee86c98d231371
https://doi.org/10.1007/978-3-642-28050-4_17

Spanning trees with many leaves: new extremal results and an improved FPT algorithm

Autor: Bonsma, P.S.

We present two lower bounds for the maximum number of leaves in a spanning tree of a graph. For connected graphs without triangles, with minimum degree at least three, we show that a spanning tree with at least (n+4)/3 leaves exists, where n is the n

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=narcis______::f8d0547d9a28bb94a1229f531c2b4a8f
https://research.utwente.nl/en/publications/spanning-trees-with-many-leaves-new-extremal-results-and-an-improved-fpt-algorithm(52a33dc4-a6e4-4b67-af65-29a969cba8c2).html

Backbone colorings for networks: tree and path backbones

Autor: Hajo Broersma, Fomin, F. V., Golovach, P. A., Gerhard Woeginger

Publikováno v: University of Twente Research Information (Pure Portal)

We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a backbone coloring for $G$ and $H$ is a proper vertex coloring $V\rightarrow \{1,

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::bc2c230c7bb9c443c6d85dee888bb50a
https://research.utwente.nl/en/publications/backbone-colorings-for-networks-tree-and-path-backbones(e59733ab-2fd6-4535-aeef-92edafe5b2d2).html

A general framework for coloring problems

In this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of coloring problems, most of which have been motivated from

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dris___00893::4fccb7a2571b6662b4fe34086a134985

A continuation of spanning 2-connected subgraphs in truncated rectangular grid graphs

A grid graph is a finite induced subgraph of the infinite 2-dimensi-onal grid defined by $Z \times Z$ and all edges between pairs of vertices from $Z \times Z$ at Euclidean distance precisely 1. An $m\times n$-rectangular grid graph is induced by all

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dris___00893::24bd52f1f0947bd4373386454503344d