Blockers and transversals

被引：46

作者：

Zenklusen, R. ^{[1
]}

Ries, B. ^{[2
]}

Picouleau, C. ^{[3
]}

de Werra, D. ^{[2
]}

Costa, M. -C. ^{[3
]}

Bentz, C. ^{[4
]}

机构：

[1] ETH, Zurich, Switzerland

[2] Ecole Polytech Fed Lausanne, CH-1015 Lausanne, Switzerland

[3] CNAM, Lab CEDRIC, Paris, France

[4] Univ Paris 11, LRI, F-91405 Orsay, France

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 13期

关键词：

Transversal; Blocker; Matching; Complete graph; Complete bipartite graph; DELETION PROBLEMS; BIPARTITE GRAPHS; MATCHINGS; COMPLEXITY;

D O I：

10.1016/j.disc.2009.01.006

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) <= nu(G) - d. We define d-transversals T as subsets of edges such that every maximum matching M has |M boolean AND T| >= d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, chains and cycles and we construct minimum d-transversals and d-blockers in these special graphs. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：4306 / 4314

页数：9

共 15 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

Berge C., 1983, Graphes

[3]

BOROS E, 2001, SIAM J COMPUT, V30, P2036

[4] Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms [J].

Boros, Endre ;

Elbassioni, Khaled ;

Gurvich, Vladimir .

JOURNAL OF GRAPH THEORY, 2006, 53 (03) :209-232

[5] NP-completeness results for edge modification problems [J].

Burzyn, Pablo ;

Bonomo, Flavia ;

Duran, Guillermo .

DISCRETE APPLIED MATHEMATICS, 2006, 154 (13) :1824-1844

[6]

CHUNG Y, 2006, 0 1 INVERSE MAXIMUM

[7] Bicolored matchings in some classes of graphs [J].

Costa, M. C. ;

de Werra, D. ;

Picouleau, C. ;

Ries, B. .

GRAPHS AND COMBINATORICS, 2007, 23 (01) :47-60

[8] PATHS TREES AND FLOWERS [J].

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03) :449-&

[9]

FOLTIN R, 2002, MULTILINGUAL WEBJOUR

[10] On complexity of special maximum matchings constructing [J].

Kamalian, R. R. ;

Mkrtchyan, V. V. .

DISCRETE MATHEMATICS, 2008, 308 (10) :1792-1800

← 1 2 →