Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

DOI10.1007/s10878-009-9276-zzbMath1220.90146MaRDI QIDQ543514

Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, Kouhei Zenmyo

Publication date: 17 June 2011

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9276-z

zbMATH Keywords

scheduling; approximation algorithm; degree; maximum flow; inapproximability; graph orientation

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Degree-constrained graph orientation: maximum satisfaction and minimum violation, Graph balancing: a special case of scheduling unrelated parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Planar orientations with low out-degree and compaction of adjacency matrices
• A combinatorial theorem in plane geometry
• Combinatorial optimization in geometry
• Balanced vertex-orderings of graphs
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Minimizing maximum indegree
• Beyond the flow decomposition barrier
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• A Faster Deterministic Maximum Flow Algorithm
• Complexity of approximating the oriented diameter of chordal graphs
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
• Computing and Combinatorics