The optimal path-matching problem
type: Item
instance of: scholarly article
title: The optimal path-matching problem
zbMATH Open document ID: 0902.05056
DOI: 10.1007/BF01215915
published in: Combinatorica
publication date: 1998-11-23T00:00:00Z
review text: Let \(T_1\), \(T_2\) be two disjoint stable sets in the vertex set \(V\) of a graph \(G\) and let \(V-(T_1 \cup T_2)\) be \(R\). If \(M_1, M_2\) are matroids on \(T_1\) and on \(T_2\), respectively, with the common rank \(r\) then a basic path-matching is defined as a collection of \(r\) vertex disjoint paths, all of whose internal vertices are in \(R\), linking a basis of \(M_1\) to a basis of \(M_2\), together with a perfect matching of the vertices of \(R\) not in any of the paths. This concept is a common generalization of the perfect matching (put \(R=V\)) and the common basis of two matroids (put \(R=\varnothing\) and let \(G\) be a perfect matching joining copies \(T_1, T_2\) of a set \(T\)). The authors give polynomial-time solvability, min-max theorems, totally dual integral polyhedral description, strongly polynomial separation algorithms for the convex hull of matchable sets of a graph, and a polynomial-time algorithm to compute the rank of a certain matrix of indeterminates.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1226323
zbMATH Keywords: path-matching
zbMATH Keywords: matroid
author: William H. Cunningham
author: James F. Geelen
reviewed by: András Recski
MaRDI profile type: Publication
cites work: The perfectly matchable subgraph polytope of an arbitrary graph
cites work: A separation algorithm for the matchable set polytope
cites work: Paths, Trees, and Flowers
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Systems of distinct representatives and linear algebra
cites work: Q5684698
cites work: Transversals and matroid partition
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Odd Minimum Cut-Sets and b-Matchings
cites work: Short proofs on the matching polyhedron
cites work: Q3818127
cites work: The Factorization of Linear Graphs
full work available at URL: https://doi.org/10.1007/bf01215915
OpenAlex ID: W3160322950
description: scientific article; zbMATH DE number 1226323