On computing an optimal semi-matching
From MaRDI portal
Publication:2408093
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
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