Waypoint routing on bounded treewidth graphs

DOI10.1016/J.IPL.2021.106165MaRDI QIDQ2234792zbMATH OpenOpenAlexFDO

Authors Šimon Schierreich, Ondřej Suchý

Publication date 19 October 2021

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

Copyright license Creative Commons Attribution 4.0 International

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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: In the extsc{Waypoint Routing Problem} one is given an undirected capacitated and weighted graph $G$, a source-destination pair $s,tinV(G)$ and a set $WsubseteqV(G)$, of emph{waypoints}. The task is to find a walk which starts at the source vertex $s$, visits, in any order, all waypoints, ends at the destination vertex $t$, respects edge capacities, that is, traverses each edge at most as many times as is its capacity, and minimizes the cost computed as the sum of costs of traversed edges with multiplicities. We study the problem for graphs of bounded treewidth and present a new algorithm for the problem working in $2^{O(mathrmtw)}cdotn$ time, significantly improving upon the previously known algorithms. We also show that this running time is optimal for the problem under Exponential Time Hypothesis.

Recommendations

• On routing disjoint paths in bounded treewidth graphs
• Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs
• scientific article; zbMATH DE number 2086374
• Routing on trees via matchings
• scientific article; zbMATH DE number 1303574
• Location routing problems on trees
• On the complexity of an optimal routing tree problem
• Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
• Optimal Bounds for Matching Routing on Trees
• On compact and efficient routing in certain graph classes

Cites work

• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• A \(c^k n\) 5-approximation algorithm for treewidth
• A subexponential parameterized algorithm for subset TSP on planar graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Graph theory
• Monadic second-order evaluations on tree-decomposable graphs
• On the complexity of \(k\)-SAT
• Parameterized algorithms
• Service chain placement in SDNs
• Shortest two disjoint paths in polynomial time
• The Traveling Salesman Problem with Many Visits to Few Cities
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Walking through waypoints
• Which problems have strongly exponential complexity?

Cited in

(2)

• DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
• Walking through waypoints

Describes a project that uses

Uses Software

• vnep-approx

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

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