Raible, Daniel ;
Fernau, Henning
Exact Elimination of Cycles in Graphs
Abstract
One of the standard basic steps in drawing hierarchical graphs
is to invert some arcs of the given graph to make the graph acyclic.
We discuss exact and parameterized algorithms for this problem. In particular we examine a graph class called $(1,n)$graphs, which contains cubic graphs. For both exact and parameterized algorithms we use a nonstandard measure approach for the analysis. The analysis of the parameterized algorithm is of special interest, as it is not an amortized analysis modelled by 'finite states' but rather a 'topdown' amortized analysis. For $(1,n)$graphs we achieve a running time of $Oh^*(1.1871^m)$ and $Oh^*(1.212^k)$, for cubic graphs $Oh^*(1.1798^m)$ and $Oh^*(1.201^k)$, respectively. As a byproduct the trivial bound of $2^n$ for {sc Feedback Vertex Set} on planar directed graphs is broken.
BibTeX  Entry
@InProceedings{raible_et_al:DSP:2007:1235,
author = {Daniel Raible and Henning Fernau},
title = {Exact Elimination of Cycles in Graphs},
booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
year = {2007},
editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
number = {07281},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1235},
annote = {Keywords: Maximum Acyclic Subgraph, Feedback Arc Set, Amortized Analysis, Exact exponential algorthms}
}
2007
Keywords: 

Maximum Acyclic Subgraph, Feedback Arc Set, Amortized Analysis, Exact exponential algorthms 
Seminar: 

07281  Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs

Related Scholarly Article: 


Issue date: 

2007 
Date of publication: 

2007 