A matching problem with side conditions
From MaRDI portal
Publication:1145707
DOI10.1016/0012-365X(80)90002-3zbMath0446.05031MaRDI QIDQ1145707
William R. Pulleyblank, Cornuéjols, Gérard
Publication date: 1980
Published in: Discrete Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)
Related Items
Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles, Approximating minimum-cost graph problems with spanning tree edges, Packings by Complete Bipartite Graphs, Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids, Path factors of bipartite graphs, Approximation Algorithms for a Network Design Problem, Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth, Decomposition theorems for square-free 2-matchings in bipartite graphs, A fast scaling algorithm for the weighted triangle-free 2-matching problem, Triangle-free 2-matchings and M-concave functions on jump systems, A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs, An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach, A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, A proof of Cunningham's conjecture on restricted subgraphs and jump systems, An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs, A model for minimizing active processor time, Matchings of cycles and paths in directed graphs, Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs, Approximating the maximum 2- and 3-edge-colorable subgraph problems, Finding maximum square-free 2-matchings in bipartite graphs, A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges, Weighted restricted 2-matching, Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs, Unnamed Item, Generalized partitions of graphs, Approximating the maximum 3-edge-colorable subgraph problem, Minimal 2-matching-covered graphs, Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem, A greedy heuristic for a minimum-weight forest problem, Packings by cliques and by finite families of graphs, Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, \((p,k)\)-coloring problems in line graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Adjacent vertices on the b-matching polyhedron
- Establishing the matching polytope
- Local Unimodularity in the Matching Polytope
- Graph Theory and Integer Programming
- Maximum matching and a polyhedron with 0,1-vertices
- Edmonds polytopes and weakly hamiltonian graphs
- The Factors of Graphs
