Spanning Trees: A Survey

被引：86

作者：

Ozeki, Kenta ^{[2
]}

Yamashita, Tomoki ^{[1
]}

机构：

[1] Kitasato Univ, Coll Liberal Arts & Sci, Minami Ku, Kanagawa 2520373, Japan

[2] Natl Inst Informat, Chiyoda Ku, Tokyo 1018430, Japan

来源：

GRAPHS AND COMBINATORICS | 2011年 / 27卷 / 01期

关键词：

Spanning trees; k-Trees; k-Ended trees; Branch vertices; k-Leaf connected; DEGREE-PRESERVING VERTICES; MINIMUM DEGREE CONDITION; NETWORK DESIGN PROBLEM; LINEAR-TIME ALGORITHM; MAXIMUM LEAF PROBLEMS; CUBIC GRAPHS; INDEPENDENT TREES; CIRCULANT GRAPHS; STEINER TREES; APPROXIMATION ALGORITHMS;

D O I：

10.1007/s00373-010-0973-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we give a survey of spanning trees. We mainly deal with spanning trees having some particular properties concerning a hamiltonian properties, for example, spanning trees with bounded degree, with bounded number of leaves, or with bounded number of branch vertices. Moreover, we also study spanning trees with some other properties, motivated from optimization aspects or application for some problems.

引用

页码：1 / 26

页数：26

共 50 条

[41] Node degree distribution in spanning trees [J].

Pozrikidis, C. .

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2016, 49 (12)

[42] Electrical flows over spanning trees [J].

Gupta, Swati ;

Khodabakhsh, Ali ;

Mortagy, Hassan ;

Nikolova, Evdokia .

MATHEMATICAL PROGRAMMING, 2022, 196 (1-2) :479-519

[43] SPANNING-TREES WITH MANY LEAVES [J].

KLEITMAN, DJ ;

WEST, DB .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1991, 4 (01) :99-106

[44] Faster generation of random spanning trees [J].

Kelner, Jonathan A. ;

Madry, Aleksander .

2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :13-21

[45] A Novel Count of the Spanning Trees of a Cube [J].

Thomas W. Mattman .

Graphs and Combinatorics, 2024, 40

[46] Improving spanning trees by upgrading nodes [J].

Krumke, SO ;

Noltemeier, H ;

Wirth, HC ;

Marathe, MV ;

Ravi, R ;

Ravi, SS ;

Sundaram, R .

THEORETICAL COMPUTER SCIENCE, 1999, 221 (1-2) :139-155

[47] A note on universal graphs for spanning trees [J].

Gyori, Ervin ;

Li, Binlong ;

Salia, Nika ;

Tompkins, Casey .

DISCRETE APPLIED MATHEMATICS, 2025, 362 :146-147

[48] A Novel Count of the Spanning Trees of a Cube [J].

Mattman, Thomas W. .

GRAPHS AND COMBINATORICS, 2024, 40 (01)

[49] Spanning Trees of Dense Directed Graphs [J].

Mycroft, Richard ;

Naia, Tassio .

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 :645-654

[50] A NOTE ON TOTAL EXCESS OF SPANNING TREES [J].

Ohnishi, Yukichika ;

Ota, Katsuhiro ;

Ozeki, Kenta .

AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2011, 8 (01) :97-103

← 1 2 3 4 5 →