Bypassing the surface embedding: approximation schemes for network design in minor-free graphs

DOI10.1145/3519935.3520049MaRDI QIDQ6083489zbMATH OpenFDO

Authors Vincent Cohen-Addad

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3519935.3520049

zbMATH Keywords

approximation schememinor-freenetwork design

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(3)

• A \(O(\log k)\)-approximation for \textsc{Directed Steiner Tree} in planar graphs
• A PTAS for k-hop MST on the Euclidean plane: improving dependency on k
• Approximation schemes for orienteering and deadline TSP in doubling metrics

This page was built for publication: Bypassing the surface embedding: approximation schemes for network design in minor-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083489)