Length-constrained path-matchings in graphs

DOI10.1002/NET.10030MaRDI QIDQ3150130zbMATH OpenOpenAlexFDO

Authors Mohammad Ghodsi, Mohammad Mahdian, Mohammad T. Hajiaghayi, Vahab S. Mirrokni

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

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

Recommendations

• Path-matching problems
• On the disjoint paths problem
• On the complexity of vertex-disjoint length-restricted path problems
• Algorithms for finding paths with multiple constraints
• On the computational complexity of length- and neighborhood-constrained path problems

Cites work

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

Cited in

(4)

• Path-matching problems
• On the computational complexity of length- and neighborhood-constrained path problems
• scientific article; zbMATH DE number 1517139 (Why is no real title available?)
• Approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem

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

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