Length-constrained path-matchings in graphs

DOI10.1002/net.10030zbMath1014.68120OpenAlexW2065600438MaRDI QIDQ3150130

Mohammad Mahdian, Mohammad Ghodsi, Vahab S. Mirrokni, Mohammad Taghi Hajiaghayi

Publication date: 29 September 2002

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.10030

zbMATH Keywords

algorithmsmatchingNP-completenesspath-matchingpseudo-matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• 1-Approximation algorithm for bottleneck disjoint path matching
• Path-matching problems
• Über die Maximalzahl kreuzungsfreier H-Wege
• The optimal path-matching problem
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Maximum number of disjoint paths connecting specified terminals in a graph
• Minimum-time line broadcast networks
• Networks communicating for each pairing of terminals
• The complexity of finding maximum disjoint paths with length constraints

This page was built for publication: Length-constrained path-matchings in graphs