On computing an optimal semi-matching

DOI10.1007/978-3-642-25870-1_23MaRDI QIDQ3104781zbMATH OpenOpenAlexFDO

Authors František Galčík, Ján Katrenič, Gabriel Semanišin

Publication date 16 December 2011

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25870-1_23

zbMATH Keywords

maximum bounded-degree semi-matching problemoptimal semi-matching

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• On computing an optimal semi-matching
• Maximum semi-matching problem in bipartite graphs
• Faster algorithms for semi-matching problems
• Semi-matchings for bipartite graphs and load balancing
• Faster algorithms for semi-matching problems (extended abstract)

Cites work

• A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
• Algorithms – ESA 2004
• Faster algorithms for semi-matching problems (extended abstract)
• Scheduling independent tasks to reduce mean finishing time
• Semi-matchings for bipartite graphs and load balancing
• Technical Note—Minimizing Average Flow Time with Parallel Machines

Cited in

(9)

• Distributed backup placement in networks
• On computing an optimal semi-matching
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Faster algorithms for semi-matching problems
• Maximum semi-matching problem in bipartite graphs
• Faster algorithms for semi-matching problems (extended abstract)
• Computing Optimal Morse Matchings
• Semi-matchings for bipartite graphs and load balancing.
• On the distributed complexity of the semi-matching problem

This page was built for publication: On computing an optimal semi-matching

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