Enumerating spanning and connected subsets in graphs and matroids

被引：0
|
作者：
Khachiyan, L.
Boros, E.
Borys, K.
Elbassioni, K.
Gurvich, V.
Makino, K.
机构：
[1] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08854 USA
[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA
[3] Max Planck Inst Informat, Saarbrucken, Germany
[4] Osaka Univ, Div Math Sci Social Syst, Grad Sch Engn Sci, Toyonaka, Osaka 5608531, Japan
来源：
ALGORITHMS - ESA 2006, PROCEEDINGS | 2006年 / 4168卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasipolynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected edge subsets of a given graph can be generated in incremental polynomial time.
引用
收藏
页码：444 / 455
页数：12
相关论文
共 50 条
  • [1] Enumerating spanning and connected subsets in graphs and matroids
    Khachiyan, Leonid
    Boros, Endre
    Borys, Konrad
    Elbassioni, Khaled
    Gurvich, Vladimir
    Makino, Kazuhisa
    JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 2007, 50 (04) : 325 - 338
  • [2] Enumerating spanning trees of graphs with an involution
    Zhang, Fuji
    Yan, Weigen
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2009, 116 (03) : 650 - 662
  • [3] On spanning connected graphs
    Lin, Cheng-Kuan
    Huang, Hua-Min
    Tan, Jimmy J. M.
    Hsu, Lih-Hsing
    DISCRETE MATHEMATICS, 2008, 308 (07) : 1330 - 1333
  • [4] Enumerating Highly-Edge-Connected Spanning Subgraphs
    Yamanaka, Katsuhisa
    Matsui, Yasuko
    Nakano, Shin-ichi
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2019, E102A (09) : 1002 - 1006
  • [5] Methods of Constructing and Enumerating the Spanning Tree of a Connected Graph
    Xu, Zhaodi
    Li, Xiaoyi
    Chou, Wanxi
    FRONTIERS OF MANUFACTURING AND DESIGN SCIENCE IV, PTS 1-5, 2014, 496-500 : 2363 - +
  • [6] A note on packing spanning trees in graphs and bases in matroids
    Bailey, Robert F.
    Newman, Mike
    Stevens, Brett
    AUSTRALASIAN JOURNAL OF COMBINATORICS, 2014, 59 : 24 - 38
  • [7] On the structure of 3-connected matroids and graphs
    Oxley, J
    Wu, HD
    EUROPEAN JOURNAL OF COMBINATORICS, 2000, 21 (05) : 667 - 688
  • [8] Count and cofactor matroids of highly connected graphs
    Garamvolgyi, Daniel
    Jordan, Tibor
    Kiraly, Csaba
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 166 : 1 - 29
  • [9] Enumerating the Number of Spanning Trees of Pyramid Graphs Based on Some Nonahedral Graphs
    Asiri, Ahmad
    Daoud, Salama Nagy
    AXIOMS, 2025, 14 (03)
  • [10] Connected rigidity matroids and unique realizations of graphs
    Jackson, B
    Jordán, T
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (01) : 1 - 29
12345