A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees

DOI10.1007/978-3-642-33090-2_31zbMath1365.68350OpenAlexW2141819463MaRDI QIDQ2912854

Fabrizio Grandoni, Marcin Pilipczuk, Piotr Sankowski, Marek Cygan, Stefano Leonardi

Publication date: 25 September 2012

Published in: Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-33090-2_31

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (4)

Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph ⋮ Unnamed Item ⋮ Pricing on Paths: A PTAS for the Highway Problem

This page was built for publication: A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees