Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Baswana, Surender
Sen, Sandeep

dblp
dblp

Not MPG Author(s):

Sen, Sandeep

BibTeX cite key*:

BaswanaSen2007

Title

Title*:

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

Journal

Journal Title*:

Random Structures & Algorithms

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Wiley

Publisher's URL:


Publisher's
Address:

New York, NY, USA

ISSN:

1042-9832

Vol, No, pp, Date

Volume*:

30

Number:

4

Publishing Date:

July 2007

Pages*:

532-563

Number of
VG Pages:


Page Start:

532

Page End:

563

Sequence Number:


DOI:

10.1002/rsa.20130

Note, Abstract, ©

Note:


(LaTeX) Abstract:

Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t-spanner of the graph G, for any t 1, is a subgraph (V,ES), ES E, such that the distance between any pair of vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t-spanner of minimum size (number of edges) has been a widely studied and well-motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t-spanner of a given weighted graph. Moreover, the size of the t-spanner computed essentially matches the worst case lower bound implied by a 43-year old girth lower bound conjecture made independently by Erds, Bollobás, and Bondy & Simonovits.Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to (t)-levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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{BaswanaSen2007,
AUTHOR = {Baswana, Surender and Sen, Sandeep},
TITLE = {A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs},
JOURNAL = {Random Structures & Algorithms},
PUBLISHER = {Wiley},
YEAR = {2007},
NUMBER = {4},
VOLUME = {30},
PAGES = {532--563},
ADDRESS = {New York, NY, USA},
MONTH = {July},
ISBN = {1042-9832},
DOI = {10.1002/rsa.20130},
}


Entry last modified by Uwe Brahm, 02/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Anja Becker
Created
02/07/2008 12:20:19 PM
Revision
1.
0.


Editor
Uwe Brahm
Anja Becker


Edit Date
02/28/2008 05:05:43 PM
07.02.2008 12:31:17