Spanning Trees: A Survey

被引：83
|
作者：
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 条
  • [1] Spanning Trees: A Survey
    Kenta Ozeki
    Tomoki Yamashita
    Graphs and Combinatorics, 2011, 27 : 1 - 26
  • [2] The number of spanning trees in a superprism
    Bogdanowicz, Zbigniew R.
    DISCRETE MATHEMATICS LETTERS, 2024, 13 : 66 - 73
  • [3] Chain-constrained spanning trees
    Olver, Neil
    Zenklusen, Rico
    MATHEMATICAL PROGRAMMING, 2018, 167 (02) : 293 - 314
  • [4] On spanning trees with few branch vertices
    Gould, Ronald J.
    Shull, Warren
    DISCRETE MATHEMATICS, 2020, 343 (0I)
  • [5] On finding spanning trees with few leaves
    Salamon, Gabor
    Wiener, Gabor
    INFORMATION PROCESSING LETTERS, 2008, 105 (05) : 164 - 169
  • [6] Spanning trees with minimum weighted degrees
    Ghodsi, Mohammad
    Mahini, Hamid
    Mirjalali, Kian
    Gharan, Shayan Oveis
    R., Amin S. Sayedi
    Zadimoghaddam, Morteza
    INFORMATION PROCESSING LETTERS, 2007, 104 (03) : 113 - 116
  • [7] Chain-constrained spanning trees
    Neil Olver
    Rico Zenklusen
    Mathematical Programming, 2018, 167 : 293 - 314
  • [8] Minimal spanning trees
    Schmerl, JH
    PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2004, 132 (02) : 333 - 340
  • [9] POPULAR SPANNING TREES
    Darmann, Andreas
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2013, 24 (05) : 655 - 677
  • [10] GENERATOR OF SPANNING TREES
    MCILROY, MD
    COMMUNICATIONS OF THE ACM, 1969, 12 (09) : 511 - &
12345