Finding independent spanning trees in partial k-trees

Xiao Zhou; Takao Nishizeki

doi:10.1007/3-540-40996-3_15

Finding independent spanning trees in partial k-trees

Xiao Zhou, Takao Nishizeki

INF - System Information Sciences

Tohoku University

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

Abstract

Spanning trees rooted at a vertex r of a graph G are independent if, for each vertex v in G, all the paths connecting v and r in the trees are pairwise internally disjoint. In this paper we give a linear-time algorithm to find the maximum number of independent spanning trees rooted at any given vertex r in partial k-trees G, that is, graphs G with tree-width bounded by a constant k.

Original language	English
Title of host publication	Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings
Editors	D.T. Lee, Shang-Hua Teng, Shang-Hua Teng
Publisher	Springer Verlag
Pages	168-179
Number of pages	12
ISBN (Print)	3540412557, 9783540412557
DOIs	https://doi.org/10.1007/3-540-40996-3_15
Publication status	Published - 2000
Event	11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 - Taipei, Taiwan, Province of China Duration: 2000 Dec 18 → 2000 Dec 20

Publication series

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

Conference

Conference	11th Annual International Symposium on Algorithms and Computation, ISAAC 2000
Country/Territory	Taiwan, Province of China
City	Taipei
Period	00/12/18 → 00/12/20

Access to Document

10.1007/3-540-40996-3_15

Cite this

Zhou, X., & Nishizeki, T. (2000). Finding independent spanning trees in partial k-trees. In D. T. Lee, S-H. Teng, & S-H. Teng (Eds.), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings (pp. 168-179). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969). Springer Verlag. https://doi.org/10.1007/3-540-40996-3_15

Zhou, Xiao ; Nishizeki, Takao. / Finding independent spanning trees in partial k-trees. Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. editor / D.T. Lee ; Shang-Hua Teng ; Shang-Hua Teng. Springer Verlag, 2000. pp. 168-179 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8867e13ccaf94db0b15c50742d4d98ec,

title = "Finding independent spanning trees in partial k-trees",

abstract = "Spanning trees rooted at a vertex r of a graph G are independent if, for each vertex v in G, all the paths connecting v and r in the trees are pairwise internally disjoint. In this paper we give a linear-time algorithm to find the maximum number of independent spanning trees rooted at any given vertex r in partial k-trees G, that is, graphs G with tree-width bounded by a constant k.",

author = "Xiao Zhou and Takao Nishizeki",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 ; Conference date: 18-12-2000 Through 20-12-2000",

year = "2000",

doi = "10.1007/3-540-40996-3_15",

language = "English",

isbn = "3540412557",

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

publisher = "Springer Verlag",

pages = "168--179",

editor = "D.T. Lee and Shang-Hua Teng and Shang-Hua Teng",

booktitle = "Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings",

address = "Germany",

}

Zhou, X & Nishizeki, T 2000, Finding independent spanning trees in partial k-trees. in DT Lee, S-H Teng & S-H Teng (eds), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1969, Springer Verlag, pp. 168-179, 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000, Taipei, Taiwan, Province of China, 00/12/18. https://doi.org/10.1007/3-540-40996-3_15

Finding independent spanning trees in partial k-trees. / Zhou, Xiao; Nishizeki, Takao.
Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. ed. / D.T. Lee; Shang-Hua Teng; Shang-Hua Teng. Springer Verlag, 2000. p. 168-179 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969).

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

TY - GEN

T1 - Finding independent spanning trees in partial k-trees

AU - Zhou, Xiao

AU - Nishizeki, Takao

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

PY - 2000

Y1 - 2000

N2 - Spanning trees rooted at a vertex r of a graph G are independent if, for each vertex v in G, all the paths connecting v and r in the trees are pairwise internally disjoint. In this paper we give a linear-time algorithm to find the maximum number of independent spanning trees rooted at any given vertex r in partial k-trees G, that is, graphs G with tree-width bounded by a constant k.

AB - Spanning trees rooted at a vertex r of a graph G are independent if, for each vertex v in G, all the paths connecting v and r in the trees are pairwise internally disjoint. In this paper we give a linear-time algorithm to find the maximum number of independent spanning trees rooted at any given vertex r in partial k-trees G, that is, graphs G with tree-width bounded by a constant k.

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

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

U2 - 10.1007/3-540-40996-3_15

DO - 10.1007/3-540-40996-3_15

M3 - Conference contribution

AN - SCOPUS:84949817386

SN - 3540412557

SN - 9783540412557

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

SP - 168

EP - 179

BT - Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings

A2 - Lee, D.T.

A2 - Teng, Shang-Hua

PB - Springer Verlag

T2 - 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000

Y2 - 18 December 2000 through 20 December 2000

ER -

Zhou X, Nishizeki T. Finding independent spanning trees in partial k-trees. In Lee DT, Teng S-H, Teng S-H, editors, Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Springer Verlag. 2000. p. 168-179. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-40996-3_15

Finding independent spanning trees in partial k-trees

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this