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 条

[31] ON TORSOR STRUCTURES ON SPANNING TREES [J].

Shokrieh, Farbod ;

Wright, Cameron .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (03) :2126-2147

[32] The facets of the spanning trees polytope [J].

Brahim Chaourar .

Mathematical Methods of Operations Research, 2022, 96 :113-121

[33] Spanning Trees on the Sierpinski Gasket [J].

Shu-Chiuan Chang ;

Lung-Chi Chen ;

Wei-Shih Yang .

Journal of Statistical Physics, 2007, 126 :649-667

[34] Low-degree spanning trees of small weight [J].

Khuller, S ;

Raghavachari, B ;

Young, N .

SIAM JOURNAL ON COMPUTING, 1996, 25 (02) :355-368

[35] Node-independent spanning trees in Gaussian networks [J].

Hussain, Zaid ;

AlBdaiwi, Bader ;

Cerny, Anton .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2017, 109 :324-332

[36] Improving minimum cost spanning trees by upgrading nodes [J].

Krumke, SO ;

Marathe, MV ;

Noltemeier, H ;

Ravi, R ;

Ravi, SS ;

Sundarum, R ;

Wirth, HC .

JOURNAL OF ALGORITHMS, 1999, 33 (01) :92-111

[37] A counterexample for the proof of implication conjecture on independent spanning trees [J].

Gopalan, Abishek ;

Ramasubramanian, Srinivasan .

INFORMATION PROCESSING LETTERS, 2013, 113 (14-16) :522-526

[38] The spectrum and spanning trees of polyominos on the torus [J].

Lu, Fuliang ;

Gong, Yajun ;

Zhou, Houchun .

JOURNAL OF MATHEMATICAL CHEMISTRY, 2014, 52 (07) :1841-1847

[39] Maintaining spanning trees of small diameter [J].

Italiano, GF ;

Ramaswami, R .

ALGORITHMICA, 1998, 22 (03) :275-304

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

Swati Gupta ;

Ali Khodabakhsh ;

Hassan Mortagy ;

Evdokia Nikolova .

Mathematical Programming, 2022, 196 :479-519

← 1 2 3 4 5 →