Enumerating spanning and connected subsets in graphs and matroids

Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

doi:10.15807/jorsj.50.325

Enumerating spanning and connected subsets in graphs and matroids

Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Electrical Engineering

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.

Original language	British English
Pages (from-to)	325-338
Number of pages	14
Journal	Journal of the Operations Research Society of Japan
Volume	50
Issue number	4
DOIs	https://doi.org/10.15807/jorsj.50.325
State	Published - Dec 2007

Keywords

Algorithm
Enumeration
Matroid
Quasi-polynomial

Access to Document

10.15807/jorsj.50.325

Cite this

@article{b03a28210c8f459b940deaf373bfcfdb,

title = "Enumerating spanning and connected subsets in graphs and matroids",

abstract = "We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.",

keywords = "Algorithm, Enumeration, Matroid, Quasi-polynomial",

author = "Leonid Khachiyan and Endre Boros and Konrad Borys and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino",

year = "2007",

month = dec,

doi = "10.15807/jorsj.50.325",

language = "British English",

volume = "50",

pages = "325--338",

journal = "Journal of the Operations Research Society of Japan",

issn = "0453-4514",

publisher = "Operations Research Society of Japan",

number = "4",

}

TY - JOUR

T1 - Enumerating spanning and connected subsets in graphs and matroids

AU - Khachiyan, Leonid

AU - Boros, Endre

AU - Borys, Konrad

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Makino, Kazuhisa

PY - 2007/12

Y1 - 2007/12

N2 - We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.

AB - We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.

KW - Algorithm

KW - Enumeration

KW - Matroid

KW - Quasi-polynomial

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

U2 - 10.15807/jorsj.50.325

DO - 10.15807/jorsj.50.325

M3 - Article

AN - SCOPUS:39649114073

SN - 0453-4514

VL - 50

SP - 325

EP - 338

JO - Journal of the Operations Research Society of Japan

JF - Journal of the Operations Research Society of Japan

IS - 4

ER -

Enumerating spanning and connected subsets in graphs and matroids

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this