Generating minimal k-vertex connected spanning subgraphs

Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino; Gabor Rudolf

doi:10.1007/978-3-540-73545-8_23

Generating minimal k-vertex connected spanning subgraphs

Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino, Gabor Rudolf

Electrical Engineering

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

9 Scopus citations

Abstract

We show that minimal k-vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed k.

Original language	British English
Title of host publication	Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings
Publisher	Springer Verlag
Pages	222-231
Number of pages	10
ISBN (Print)	9783540735441
DOIs	https://doi.org/10.1007/978-3-540-73545-8_23
State	Published - 2007
Event	13th Annual International Computing and Combinatorics Conference, COCOON 2007 - Banff, Canada Duration: 16 Jul 2007 → 19 Jul 2007

Publication series

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

Conference

Conference	13th Annual International Computing and Combinatorics Conference, COCOON 2007
Country/Territory	Canada
City	Banff
Period	16/07/07 → 19/07/07

Access to Document

10.1007/978-3-540-73545-8_23

Cite this

Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Makino, K., & Rudolf, G. (2007). Generating minimal k-vertex connected spanning subgraphs. In Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings (pp. 222-231). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4598 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73545-8_23

Boros, Endre ; Borys, Konrad ; Elbassioni, Khaled et al. / Generating minimal k-vertex connected spanning subgraphs. Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings. Springer Verlag, 2007. pp. 222-231 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1af0c291e2444fd18e436716e65b8551,

title = "Generating minimal k-vertex connected spanning subgraphs",

abstract = "We show that minimal k-vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed k.",

author = "Endre Boros and Konrad Borys and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino and Gabor Rudolf",

year = "2007",

doi = "10.1007/978-3-540-73545-8_23",

language = "British English",

isbn = "9783540735441",

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

publisher = "Springer Verlag",

pages = "222--231",

booktitle = "Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings",

address = "Germany",

note = "13th Annual International Computing and Combinatorics Conference, COCOON 2007 ; Conference date: 16-07-2007 Through 19-07-2007",

}

Boros, E, Borys, K, Elbassioni, K, Gurvich, V, Makino, K & Rudolf, G 2007, Generating minimal k-vertex connected spanning subgraphs. in Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4598 LNCS, Springer Verlag, pp. 222-231, 13th Annual International Computing and Combinatorics Conference, COCOON 2007, Banff, Canada, 16/07/07. https://doi.org/10.1007/978-3-540-73545-8_23

Generating minimal k-vertex connected spanning subgraphs. / Boros, Endre; Borys, Konrad; Elbassioni, Khaled et al.
Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings. Springer Verlag, 2007. p. 222-231 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4598 LNCS).

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

TY - GEN

T1 - Generating minimal k-vertex connected spanning subgraphs

AU - Boros, Endre

AU - Borys, Konrad

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Makino, Kazuhisa

AU - Rudolf, Gabor

PY - 2007

Y1 - 2007

N2 - We show that minimal k-vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed k.

AB - We show that minimal k-vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed k.

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

U2 - 10.1007/978-3-540-73545-8_23

DO - 10.1007/978-3-540-73545-8_23

M3 - Conference contribution

AN - SCOPUS:37849015274

SN - 9783540735441

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

SP - 222

EP - 231

BT - Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings

PB - Springer Verlag

T2 - 13th Annual International Computing and Combinatorics Conference, COCOON 2007

Y2 - 16 July 2007 through 19 July 2007

ER -

Boros E, Borys K, Elbassioni K, Gurvich V, Makino K, Rudolf G. Generating minimal k-vertex connected spanning subgraphs. In Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings. Springer Verlag. 2007. p. 222-231. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73545-8_23

Generating minimal k-vertex connected spanning subgraphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this