A fixed parameter tractable approximation scheme for the optimal cut graph of a surface

V. Cohen Addad, A.N. De Mesmay, in:, Springer, 2015, pp. 386–398.


Conference Paper | Published | English
Author
;
Department
Series Title
LNCS
Abstract
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)n3. 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.
Publishing Year
Date Published
2015-09-01
Volume
9294
Page
386 - 398
Conference
ESA: European Symposium on Algorithms
Conference Location
Patras, Greece
Conference Date
2015-09-14 – 2015-09-16
IST-REx-ID

Cite this

Cohen Addad V, De Mesmay AN. A fixed parameter tractable approximation scheme for the optimal cut graph of a surface. In: Vol 9294. Springer; 2015:386-398. doi:10.1007/978-3-662-48350-3_33
Cohen Addad, V., & De Mesmay, A. N. (2015). A fixed parameter tractable approximation scheme for the optimal cut graph of a surface (Vol. 9294, pp. 386–398). Presented at the ESA: European Symposium on Algorithms, Patras, Greece: Springer. https://doi.org/10.1007/978-3-662-48350-3_33
Cohen Addad, Vincent, and Arnaud N De Mesmay. “A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface,” 9294:386–98. Springer, 2015. https://doi.org/10.1007/978-3-662-48350-3_33.
V. Cohen Addad and A. N. De Mesmay, “A fixed parameter tractable approximation scheme for the optimal cut graph of a surface,” presented at the ESA: European Symposium on Algorithms, Patras, Greece, 2015, vol. 9294, pp. 386–398.
Cohen Addad V, De Mesmay AN. 2015. A fixed parameter tractable approximation scheme for the optimal cut graph of a surface. ESA: European Symposium on Algorithms, LNCS, vol. 9294. 386–398.
Cohen Addad, Vincent, and Arnaud N. De Mesmay. A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface. Vol. 9294, Springer, 2015, pp. 386–98, doi:10.1007/978-3-662-48350-3_33.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar