1-Approximation algorithm for bottleneck disjoint path matching

DOI10.1016/0020-0190(95)00031-7MaRDI QIDQ672495zbMATH OpenOpenAlexFDO

Authors Alak Kumar Datta, Ranjan Kumar Sen

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00031-7

zbMATH Keywords

graphalgorithmsmatchingapproximation algorithmspath matching

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cites work

• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• An O(logn) parallel connectivity algorithm
• Combinatorial optimization. Networks and matroids
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Maximum matching and a polyhedron with 0,1-vertices
• Parallel concepts in graph theory
• Path-matching problems

Cited in

(3)

• Approximate spanning cactus
• Balanced paths in acyclic networks: Tractable cases and related approaches
• Length-constrained path-matchings in graphs

This page was built for publication: 1-Approximation algorithm for bottleneck disjoint path matching

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