Waypoint routing on bounded treewidth graphs

DOI10.1016/j.ipl.2021.106165zbMath1472.68121arXiv2007.04008OpenAlexW3041909641MaRDI QIDQ2234792

Šimon Schierreich, Ondřej Suchý

Publication date: 19 October 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.04008

zbMATH Keywords

treewidthgraph algorithmsfixed-parameter tractabilitysubset TSPwaypoint routing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Uses Software

• vnep-approx

Cites Work

• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• Which problems have strongly exponential complexity?
• Service chain placement in SDNs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Graph Theory
• The Traveling Salesman Problem with Many Visits to Few Cities
• Shortest Two Disjoint Paths in Polynomial Time
• A subexponential parameterized algorithm for Subset TSP on planar graphs
• Parameterized Algorithms
• Walking through waypoints
• On the complexity of \(k\)-SAT

This page was built for publication: Waypoint routing on bounded treewidth graphs