Waypoint routing on bounded treewidth graphs

DOI10.1016/J.IPL.2021.106165zbMATH Open1472.68121arXiv2007.04008OpenAlexW3041909641MaRDI QIDQ2234792FDOQ2234792

Authors: Šimon Schierreich, Ondřej Suchý 

Publication date: 19 October 2021

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

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.

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

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

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)

Cites Work

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

Cited In (2)

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

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)