On computing an optimal semi-matching

DOI10.1007/s00453-016-0182-3zbMath1371.05227OpenAlexW2463035494MaRDI QIDQ2408093

Ján Katrenič, František Galčík, Gabriel Semanisin

Publication date: 9 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0182-3

zbMATH Keywords

algorithmbipartite graphcombinatorial optimizationsemi-matchingload-balancing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)

Cites Work

• A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
• Faster Algorithms for Semi-Matching Problems
• Maximum semi-matching problem in bipartite graphs
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling independent tasks to reduce mean finishing time
• Distributed 2-Approximation Algorithm for the Semi-matching Problem
• Approximating Semi-matchings in Streaming and in Two-Party Communication
• Multiplying matrices faster than coppersmith-winograd
• Algorithms – ESA 2004
• Semi-matchings for bipartite graphs and load balancing
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Technical Note—Minimizing Average Flow Time with Parallel Machines

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