The unimodular intersection problem

DOI10.1016/J.ORL.2015.09.005MaRDI QIDQ1785442zbMATH OpenOpenAlexFDO

Authors Volker Kaibel, Shmuel Onn, Pauline Sarrabezolles

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.04301

zbMATH Keywords

combinatorial optimizationgraphinteger programmingmatchingpathunimodular

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: We show that finding minimally intersecting $n$ paths from $s$ to $t$ in a directed graph or $n$ perfect matchings in a bipartite graph can be done in polynomial time. This holds more generally for unimodular set systems.

Recommendations

• scientific article; zbMATH DE number 2086910
• The optimal path-matching problem
• On the disjoint paths problem
• scientific article; zbMATH DE number 3912430
• Path-matching problems

Cites work

• Finding paths with minimum shared edges
• scientific article; zbMATH DE number 3628712 (Why is no real title available?)
• Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
• Nonlinear discrete optimization. An algorithmic theory
• The minimum vulnerability problem

Cited in

(4)

• Shifted matroid optimization
• Approximate separable multichoice optimization over monotone systems
• scientific article; zbMATH DE number 4173033 (Why is no real title available?)
• Optimization over degree sequences

This page was built for publication: The unimodular intersection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785442)