scientific article; zbMATH DE number 6783450

zbMath1376.68059MaRDI QIDQ5365098

MohammadHossein Bateni, Nitish Korula, Dániel Marx, Alina Ene, Chandra Chekuri, Mohammad Taghi Hajiaghayi

Publication date: 29 September 2017

Full work available at URL: http://dl.acm.org/citation.cfm?id=2133115

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (12)

A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ On the Exact Solution of Prize-Collecting Steiner Tree Problems ⋮ Improved Steiner tree algorithms for bounded treewidth ⋮ FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM ⋮ Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio ⋮ Unnamed Item ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree

This page was built for publication: