MPI-INF D1 Publications: Journal Article: Shortest paths in digraphs of small treewidth. {Part} I, {Sequential} algorithms

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Goto entry point

Author, Editor(s)

Author(s):

Chaudhuri, Shiva
Zaroliagis, Christos

dblp
dblp

BibTeX cite key*:

ChaudhuriZaroliagis2000

Title

Title*:

Shortest paths in digraphs of small treewidth. Part I, Sequential algorithms

Journal

Journal Title*:	Algorithmica	Journal's URL:	http://link.springer-ny.com/link/service/journals/00453/
Download URL for the article:		Language:	English

Publisher

Publisher's Name:	Springer	Publisher's URL:	http://www.springer-ny.com/
Publisher's Address:	New York, USA	ISSN:	0178-4617

Vol, No, pp, Date

Volume*:	27	Number:	3/4
Publishing Date:	2000
Pages*:	212-226	Number of VG Pages:
Page Start:		Page End:
Sequence Number:		DOI:

Note, Abstract, ©

Note:
(LaTeX) Abstract:	We consider the problem of preprocessing an n -vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered. We give algorithms that depend on the treewidth of the input graph. When the treewidth is a constant, our algorithms can answer distance queries in O(α(n)) time after O(n) preprocessing. This improves upon previously known results for the same problem. We also give a dynamic algorithm which, after a change in an edge weight, updates the data structure in time O(nβ) , for any constant 0 < β < 1 . Furthermore, an algorithm of independent interest is given: computing a shortest path tree, or finding a negative cycle in linear time.
URL for the Abstract:
Categories, Keywords:
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	Expert
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{ChaudhuriZaroliagis2000,
AUTHOR = {Chaudhuri, Shiva and Zaroliagis, Christos},
TITLE = {Shortest paths in digraphs of small treewidth. {Part} I, {Sequential} algorithms},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2000},
NUMBER = {3/4},
VOLUME = {27},
PAGES = {212--226},
ADDRESS = {New York, USA},
ISBN = {0178-4617},
}

Entry last modified by Christine Kiesel, 03/02/2010

Edit History (please click the blue arrow to see the details)

	Editor(s) Anja Becker	Created 03/14/2001 15:13:28
Revisions 6. 5. 4. 3. 2.	Editor(s) Christine Kiesel Uwe Brahm Uwe Brahm Uwe Brahm Uwe Brahm	Edit Dates 30.05.2005 15:35:08 05/02/2001 11:27:34 AM 04/09/2001 12:12:09 PM 04/09/2001 12:07:55 PM 04.04.2001 14:50:08

Attachment Section