Graph spanners: A tutorial review

Reyan Ahmed; Greg Bodwin; Faryad Darabi Sahneh; Keaton Hamm; Mohammad Javad Latifi Jebelli; Stephen Kobourov; Richard Spence

doi:10.1016/j.cosrev.2020.100253

Graph spanners: A tutorial review

Reyan Ahmed
, Greg Bodwin
, Faryad Darabi Sahneh
, Keaton Hamm
, Mohammad Javad Latifi Jebelli
, Stephen Kobourov
, Richard Spence

Research output: Contribution to journal › Review article › peer-review

84 Scopus citations

Abstract

This survey provides a guiding reference to researchers seeking an overview of the large body of literature about graph spanners. It surveys the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.

Original language	English (US)
Article number	100253
Journal	Computer Science Review
Volume	37
DOIs	https://doi.org/10.1016/j.cosrev.2020.100253
State	Published - Aug 2020
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.cosrev.2020.100253

Cite this

@article{dda9929d7b654b179a79ff2c5c7af47d,

title = "Graph spanners: A tutorial review",

abstract = "This survey provides a guiding reference to researchers seeking an overview of the large body of literature about graph spanners. It surveys the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.",

author = "Reyan Ahmed and Greg Bodwin and Sahneh, \{Faryad Darabi\} and Keaton Hamm and \{Latifi Jebelli\}, \{Mohammad Javad\} and Stephen Kobourov and Richard Spence",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2020",

month = aug,

doi = "10.1016/j.cosrev.2020.100253",

language = "English (US)",

volume = "37",

journal = "Computer Science Review",

issn = "1574-0137",

publisher = "Elsevier Ireland Ltd",

}

TY - JOUR

T1 - Graph spanners

T2 - A tutorial review

AU - Ahmed, Reyan

AU - Bodwin, Greg

AU - Sahneh, Faryad Darabi

AU - Hamm, Keaton

AU - Latifi Jebelli, Mohammad Javad

AU - Kobourov, Stephen

AU - Spence, Richard

PY - 2020/8

Y1 - 2020/8

N2 - This survey provides a guiding reference to researchers seeking an overview of the large body of literature about graph spanners. It surveys the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.

AB - This survey provides a guiding reference to researchers seeking an overview of the large body of literature about graph spanners. It surveys the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.

UR - https://www.scopus.com/pages/publications/85090284402

UR - https://www.scopus.com/pages/publications/85090284402#tab=citedBy

U2 - 10.1016/j.cosrev.2020.100253

DO - 10.1016/j.cosrev.2020.100253

M3 - Review article

AN - SCOPUS:85090284402

SN - 1574-0137

VL - 37

JO - Computer Science Review

JF - Computer Science Review

M1 - 100253

ER -

Graph spanners: A tutorial review

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this