Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
verfasst von : Vincent Cohen-Addad, Arnaud de Mesmay
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a graph
G
cellularly embedded on a surface Σ of genus
g
, a cut graph is a subgraph of
G
such that cutting Σ along
G
yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any
ε
> 0, we show how to compute a (1 +
ε
) approximation of the shortest cut graph in time
f
(
ε
,
g
)
n
3
.
Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest.