A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
From MaRDI portal
Publication:3452802
DOI10.1007/978-3-662-48350-3_33zbMath1466.68072arXiv1507.01688MaRDI QIDQ3452802
Arnaud de Mesmay, Vincent Cohen-Addad
Publication date: 19 November 2015
Published in: Algorithms - ESA 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.01688
68R10: Graph theory (including graph drawing) in computer science
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
05C10: Planar graphs; geometric and topological aspects of graph theory
68W25: Approximation algorithms
68U03: Computational aspects of digital topology
Related Items
Unnamed Item, Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack, A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
Cites Work
- Tree-width of hypergraphs and surface duality
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Graph minors. X: Obstructions to tree-decomposition
- Optimally cutting a surface into a disk
- Approximation algorithms via contraction decomposition
- An O ( n log n ) approximation scheme for Steiner tree in planar graphs
- On self duality of pathwidth in polyhedral graph embeddings
- A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- Dynamic programming for graphs on surfaces
- Unnamed Item
- Unnamed Item
- Unnamed Item