### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. (2009) *Bounded-degree techniques accelerate some parameterized graph algorithms*.

** BibTeX **

@conference{

Damaschke2009,

author={Damaschke, Peter},

title={Bounded-degree techniques accelerate some parameterized graph algorithms},

booktitle={4th International Workshop on Parameterized and Exact Computation IWPEC 2009, Lecture Notes in Computer Science},

isbn={978-3-642-11268-3},

pages={98-109},

abstract={Many algorithms for FPT graph problems are search tree algorithms with sophisticated local branching rules. But it has also been noticed that using the global structure of input graphs complements the the search tree paradigm. Here we prove some new results based on the global structure of bounded-degree graphs after branching away the high-degree vertices. Some techniques and structural results are generic and should find more applications. First, we decompose a graph by ``separating'' branchings into cheaper or smaller
components wich are then processed separately. Using this idea we accelerate the O(1.3803^k) time algorithm for counting the vertex covers of size k (Mölle, Richter, and Rossmanith, 2006) to O(1.3740^k). Next we characterize the graphs where no edge is in three conflict triples, i.e.,
triples of vertices with exactly two edges. This theorem may find interest in graph theory, and it yields an O(1.47^k) time algorithm for Cluster Deletion, improving upon the previous O(1.53^k) (Gramm, Guo, Hüffner, Niedermeier, 2004). Cluster Deletion is the problem of deleting k edges to destroy all conflict triples and get a disjoint union of cliques. For graphs where every edge is in O(1) conflict triples we show a nice dichotomy: The graph or its complement has degree O(1). This opens the possibility for future improvements via the above decomposition technique.},

year={2009},

keywords={parameterized algorithm, vertex cover, clustering, graph separator, vertex degree},

}

** RefWorks **

RT Conference Proceedings

SR Print

ID 106555

A1 Damaschke, Peter

T1 Bounded-degree techniques accelerate some parameterized graph algorithms

YR 2009

T2 4th International Workshop on Parameterized and Exact Computation IWPEC 2009, Lecture Notes in Computer Science

SN 978-3-642-11268-3

SP 98

AB Many algorithms for FPT graph problems are search tree algorithms with sophisticated local branching rules. But it has also been noticed that using the global structure of input graphs complements the the search tree paradigm. Here we prove some new results based on the global structure of bounded-degree graphs after branching away the high-degree vertices. Some techniques and structural results are generic and should find more applications. First, we decompose a graph by ``separating'' branchings into cheaper or smaller
components wich are then processed separately. Using this idea we accelerate the O(1.3803^k) time algorithm for counting the vertex covers of size k (Mölle, Richter, and Rossmanith, 2006) to O(1.3740^k). Next we characterize the graphs where no edge is in three conflict triples, i.e.,
triples of vertices with exactly two edges. This theorem may find interest in graph theory, and it yields an O(1.47^k) time algorithm for Cluster Deletion, improving upon the previous O(1.53^k) (Gramm, Guo, Hüffner, Niedermeier, 2004). Cluster Deletion is the problem of deleting k edges to destroy all conflict triples and get a disjoint union of cliques. For graphs where every edge is in O(1) conflict triples we show a nice dichotomy: The graph or its complement has degree O(1). This opens the possibility for future improvements via the above decomposition technique.

LA eng

OL 30