On element-connectivity preserving graph simplification

Chandra Chekuri; Thapanapong Rukkanchanunt; Chao Xu

doi:10.1007/978-3-662-48350-3_27

On element-connectivity preserving graph simplification

Chandra Chekuri, Thapanapong Rukkanchanunt, Chao Xu

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The notion of element-connectivity has found several important applications in network design and routing problems. We focus on a reduction step that preserves the element-connectivity [18,4,3], which when applied repeatedly allows one to reduce the original graph to a simpler one. This pre-processing step is a crucial ingredient in several applications. In this paper we revisit this reduction step and provide a new proof via the use of setpairs. Our main contribution is algorithmic results for several basic problems on element-connectivity including the problem of achieving the aforementioned graph simplification.We utilize the underlying submodularity properties of element-connectivity to derive faster algorithms.

Original language	English (US)
Title of host publication	Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
Editors	Nikhil Bansal, Irene Finocchi
Publisher	Springer
Pages	313-324
Number of pages	12
ISBN (Print)	9783662483497
DOIs	https://doi.org/10.1007/978-3-662-48350-3_27
State	Published - 2015
Event	23rd European Symposium on Algorithms, ESA 2015 - Patras, Greece Duration: Sep 14 2015 → Sep 16 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9294
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	23rd European Symposium on Algorithms, ESA 2015
Country/Territory	Greece
City	Patras
Period	9/14/15 → 9/16/15

Keywords

Bisubmodular
Element-connectivity
Gomory-Hu tree
Reduction

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-662-48350-3_27

Library availability

Discover UIUC Full Text

Cite this

Chekuri, C., Rukkanchanunt, T., & Xu, C. (2015). On element-connectivity preserving graph simplification. In N. Bansal, & I. Finocchi (Eds.), Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings (pp. 313-324). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294). Springer. https://doi.org/10.1007/978-3-662-48350-3_27

On element-connectivity preserving graph simplification. / Chekuri, Chandra; Rukkanchanunt, Thapanapong; Xu, Chao.
Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. ed. / Nikhil Bansal; Irene Finocchi. Springer, 2015. p. 313-324 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chekuri, C, Rukkanchanunt, T & Xu, C 2015, On element-connectivity preserving graph simplification. in N Bansal & I Finocchi (eds), Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9294, Springer, pp. 313-324, 23rd European Symposium on Algorithms, ESA 2015, Patras, Greece, 9/14/15. https://doi.org/10.1007/978-3-662-48350-3_27

Chekuri C, Rukkanchanunt T, Xu C. On element-connectivity preserving graph simplification. In Bansal N, Finocchi I, editors, Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Springer. 2015. p. 313-324. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48350-3_27

Chekuri, Chandra ; Rukkanchanunt, Thapanapong ; Xu, Chao. / On element-connectivity preserving graph simplification. Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. editor / Nikhil Bansal ; Irene Finocchi. Springer, 2015. pp. 313-324 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a5ec7bd218e7462ea2250c73fa93a7ac,

title = "On element-connectivity preserving graph simplification",

abstract = "The notion of element-connectivity has found several important applications in network design and routing problems. We focus on a reduction step that preserves the element-connectivity [18,4,3], which when applied repeatedly allows one to reduce the original graph to a simpler one. This pre-processing step is a crucial ingredient in several applications. In this paper we revisit this reduction step and provide a new proof via the use of setpairs. Our main contribution is algorithmic results for several basic problems on element-connectivity including the problem of achieving the aforementioned graph simplification.We utilize the underlying submodularity properties of element-connectivity to derive faster algorithms.",

keywords = "Bisubmodular, Element-connectivity, Gomory-Hu tree, Reduction",

author = "Chandra Chekuri and Thapanapong Rukkanchanunt and Chao Xu",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 23rd European Symposium on Algorithms, ESA 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

year = "2015",

doi = "10.1007/978-3-662-48350-3_27",

language = "English (US)",

isbn = "9783662483497",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "313--324",

editor = "Nikhil Bansal and Irene Finocchi",

booktitle = "Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings",

address = "Germany",

}

TY - GEN

T1 - On element-connectivity preserving graph simplification

AU - Chekuri, Chandra

AU - Rukkanchanunt, Thapanapong

AU - Xu, Chao

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - The notion of element-connectivity has found several important applications in network design and routing problems. We focus on a reduction step that preserves the element-connectivity [18,4,3], which when applied repeatedly allows one to reduce the original graph to a simpler one. This pre-processing step is a crucial ingredient in several applications. In this paper we revisit this reduction step and provide a new proof via the use of setpairs. Our main contribution is algorithmic results for several basic problems on element-connectivity including the problem of achieving the aforementioned graph simplification.We utilize the underlying submodularity properties of element-connectivity to derive faster algorithms.

AB - The notion of element-connectivity has found several important applications in network design and routing problems. We focus on a reduction step that preserves the element-connectivity [18,4,3], which when applied repeatedly allows one to reduce the original graph to a simpler one. This pre-processing step is a crucial ingredient in several applications. In this paper we revisit this reduction step and provide a new proof via the use of setpairs. Our main contribution is algorithmic results for several basic problems on element-connectivity including the problem of achieving the aforementioned graph simplification.We utilize the underlying submodularity properties of element-connectivity to derive faster algorithms.

KW - Bisubmodular

KW - Element-connectivity

KW - Gomory-Hu tree

KW - Reduction

UR - http://www.scopus.com/inward/record.url?scp=84945535090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945535090&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48350-3_27

DO - 10.1007/978-3-662-48350-3_27

M3 - Conference contribution

AN - SCOPUS:84945535090

SN - 9783662483497

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 313

EP - 324

BT - Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings

A2 - Bansal, Nikhil

A2 - Finocchi, Irene

PB - Springer

T2 - 23rd European Symposium on Algorithms, ESA 2015

Y2 - 14 September 2015 through 16 September 2015

ER -

On element-connectivity preserving graph simplification

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this