Shortest paths in digraphs of small treewidth. I: Sequential algorithms
type: Item
instance of: scholarly article
title: Shortest paths in digraphs of small treewidth. I: Sequential algorithms
zbMATH Open document ID: 0960.05097
published in: Algorithmica
publication date: 2001-05-17T00:00:00Z
review text: An algorithm is developed for answering shortest path queries on graphs with constant treewidth (i.e., partial \(k\)-trees for constant \(k\)), by employing an amount of preprocessing which is linear in the size of the graph. Distance queries can be answered in time proportional to the inverse of the Ackermann function evaluated at the number \(n\) of vertices. A sublinear algorithm is given for updating edge weights dynamically.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1496842
zbMATH Keywords: shortest path
zbMATH Keywords: treewidth
zbMATH Keywords: partial \(k\)-trees
author: Shiva Chaudhuri
author: Christos Zaroliagis
reviewed by: Charles J. Colbourn
MaRDI profile type: Publication
full work available at URL: s004530010016
OpenAlex ID: W2071362870
DOI: 10.1007/S004530010016
Recommended article: Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
Recommended article: Shortest path queries in digraphs of small treewidth
Recommended article: Optimal parallel shortest paths in small treewidth digraphs
Recommended article: Q4255109
Recommended article: Q4343703
Recommended article: Approximating Pathwidth for Graphs of Small Treewidth
Recommended article: Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
Recommended article: Q3839955
Recommended article: Shortest paths in almost acyclic graphs
Recommended article: Semi-dynamic shortest paths and breadth-first search in digraphs
description: scientific article; zbMATH DE number 1496842