Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover

DOI10.1007/978-3-540-75520-3_17zbMath1151.05329OpenAlexW1504891601MaRDI QIDQ3527209

Raphael Yuster, Noga Alon

Publication date: 25 September 2008

Published in: Algorithms – ESA 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-75520-3_17

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Equistable simplicial, very well-covered, and line graphs ⋮ Approximating Edge Dominating Set in Dense Graphs ⋮ Subset matching and edge coloring in bipartite graphs ⋮ Approximating edge dominating set in dense graphs

This page was built for publication: Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover