Polynomial Time Algorithm for Shortest Paths in Interval Temporal Graphs

Autor:	Anuj Jain, Sartaj Sahni
Jazyk:	angličtina
Rok vydání:	2024
Předmět:	interval temporal graphs contact sequence temporal graphs shortest paths Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95
Zdroj:	Algorithms, Vol 17, Iss 10, p 468 (2024)
Druh dokumentu:	article
ISSN:	1999-4893
DOI:	10.3390/a17100468
Popis:	We develop a polynomial time algorithm for the single-source all destinations shortest paths problem for interval temporal graphs (ITGs). While a polynomial time algorithm for this problem is known for contact sequence temporal graphs (CSGs), no such prior algorithm is known for ITGs. We benchmark our ITG algorithm against that for CSGs using datasets that can be solved using either algorithm. Using synthetic datasets, experimentally, we show that our algorithm for ITGs obtains a speedup of up to 32.5 relative to the state-of-the-art algorithm for CSGs.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/d65580bfc3824b6d8e54edc7d5446fdb Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.