Matchings of cycles and paths in directed graphs
Tóm tắt
In this paper we present a Berge-Tutte-type theorem for a matching problem in directed graphs. This extends the maximum matching problem in undirected graphs, the maximum even factor problem in weakly symmetric directed graphs proposed by W. H. Cunningham and J. F. Geelen in [6], and a packing problem for cycles and edges in undirected graphs. We show an Edmonds-Gallai-type structural description of a canonical set attaining the minimum in the formula. We also give a generalization of the matching matroid to this concept.
Tài liệu tham khảo
G. Cornuéjols and D. Hartvigsen: An extension of matching theory, Journal of Combinatorial Theory Ser. B 40 (1986), 285–296.
G. Cornuéjols, D. Hartvigsen and W. Pulleyblank: Packing subgraphs in a graph, Op. Res. Letters, (1982), 139–143.
G. Cornuéjols and W. Pulleyblank: A matching problem with side conditions, Discrete Mathematics 29 (1980), 135–159.
G. Cornuéjols and W. Pulleyblank: Critical graphs, matchings and tours or a hierarchy of the travelling salesman problem, Combinatorica 3(1) (1983), 35–52.
W. H. Cunningham: Matching, Matroids and Extensions, Math. Program. Ser. B 91(3) (2002), 515–542.
W. H. Cunningham and J. F. Geelen: The Optimal Path-Matching Problem, Combinatorica 17(3) (1997), 315–336.
J. Edmonds: Paths, trees, and flowers, Canadian Journal of Mathematics 17 (1965), 449–467.
S. Felsner: Orthogonal structures in directed graphs, Journal of Combinatorial Theory Ser. B 57(2) (1993), 309–321.
A. Frank and L. Szegő: A Note on the Path-Matching Formula, J. of Graph Theory 41(2) (2002), 110–119.
T. Gallai: Maximale Systeme unabhängiger Kanten, A Magyar Tudományos Akadémia Matematika Kutatóintézetének Közleményei 9 (1964), 401–413.
J. Geelen: An algebraic approach to matching problems, manuscript.
T. Király and M. Makai: On polyhedra related to even factors, Proceedings of 10th International IPCO Conference, D. Bienstock, G. Nemhauser (eds.), Lecture Notes in Computer Science, Springer, 2004, 416–430.
Z. Király and J. Szabó: Generalized induced factor problems, Egres Technical Report, 2002.
M. Loebl and S. Poljak: Efficient Subgraph Packing, Journal of Combinatorial Theory Ser. B 59 (1993), 106–121.
L. Lovász: On determinants, matchings and random algorithms, in Fundamentals of Computational Theory (L. Budach, ed.), Akademie-Verlag, Berlin, 1979, 565–574.
L. Lovász and M. D. Plummer: Matching Theory, Akadémiai Kiadó, Budapest, 1986.
Gy. Pap and L. Szegő: On the Maximum Even Factor in Weakly Symmetric Graphs, Journal of Combinatorial Theory Ser. B 91(2) (2004), 201–213.