Universität zu Köln

Amiri, Saeed Akhoondian ORCID: 0000-0002-7402-2662, Foerster, Klaus-Tycho ORCID: 0000-0003-4635-4480 and Schmid, Stefan (2020). Walking Through Waypoints. Algorithmica, 82 (7). S. 1784 - 1813. NEW YORK: SPRINGER. ISSN 1432-0541

Full text not available from this repository.

Abstract

We initiate the study of a fundamental combinatorial problem: Given a capacitated graph G = (V, E), find a shortest walk (route) from a source s. V to a destination t. V that includes all vertices specified by a set WP. V : the waypoints. This Waypoint Routing Problem finds immediate applications in the context of modern networked systems. Our main contribution is an exact polynomial-time algorithm for graphs of bounded treewidth. We also show that if the number of waypoints is logarithmically bounded, exact polynomial-time algorithms exist even for general graphs. Our two algorithms provide an almost complete characterization of what can be solved exactly in polynomial time: we show that more general problems (e.g., on grid graphs of maximum degree 3, with slightly more waypoints) are computationally intractable.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Amiri, Saeed Akhoondian UNSPECIFIED orcid.org/0000-0002-7402-2662 UNSPECIFIED Foerster, Klaus-Tycho UNSPECIFIED orcid.org/0000-0003-4635-4480 UNSPECIFIED Schmid, Stefan UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-328664
DOI:	10.1007/s00453-020-00672-z
Journal or Publication Title:	Algorithmica
Volume:	82
Number:	7
Page Range:	S. 1784 - 1813
Date:	2020
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1432-0541
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language EFFICIENT PARALLEL ALGORITHMS; MAXIMUM DISJOINT PATHS; CONNECTIVITY Multiple languages Computer Science, Software Engineering; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/32866