A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface

DOI10.1007/978-3-662-48350-3_33zbMath1466.68072arXiv1507.01688OpenAlexW1849364625MaRDI 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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25) Computational aspects of digital topology (68U03)

Related Items (3)

A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface ⋮ Unnamed Item ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface