1-Approximation algorithm for bottleneck disjoint path matching

DOI10.1016/0020-0190(95)00031-7zbMath1004.68595OpenAlexW2048149203MaRDI QIDQ672495

Ranjan Kumar Sen, Alak Kumar Datta

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

algorithmsgraphmatchingapproximation algorithmspath matching

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items

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

Cites Work

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