Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families

DOI10.1007/978-3-540-73545-8_50MaRDI QIDQ3608875zbMATH OpenOpenAlexFDO

Authors Andrzej Czygrinow, Michal Hanckowiak

Publication date 6 March 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73545-8_50

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Distributed algorithms (68W15)

Recommendations

• Distributed algorithms for weighted problems in sparse graphs
• Distributed Almost Exact Approximations for Minor-Closed Families
• Distributed Weighted Matching
• Efficient Distributed Weighted Matchings on Trees
• Distributed approximate matching

Cited in

(5)

• Distributed algorithms for weighted problems in sparse graphs
• Almost-Tight Distributed Minimum Cut Algorithms
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Distributed minimum dominating set approximations in restricted families of graphs
• Distributed Almost Exact Approximations for Minor-Closed Families

This page was built for publication: Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families

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