GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE

DOI10.1142/S0129054111008246zbMath1216.68114OpenAlexW2001855339MaRDI QIDQ2997922

Yuichi Asahiro, Jesper Jansson, Hirotaka Ono, Eiji Miyano

Publication date: 10 May 2011

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054111008246

zbMATH Keywords

schedulingapproximation algorithmmaximum flowhardness of approximationgraph orientation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (4)

Graph balancing: a special case of scheduling unrelated parallel machines ⋮ Graph orientation with splits ⋮ Graph Orientation with Edge Modifications ⋮ Degree-constrained graph orientation: maximum satisfaction and minimum violation

Cites Work

• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Minimizing maximum indegree
• Beyond the flow decomposition barrier
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Planar Formulae and Their Uses
• The Recognition of Series Parallel Digraphs
• Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
• Complexity of automaton identification from given data
• Handbook of Graph Theory
• Unnamed Item
• Unnamed Item

This page was built for publication: GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE