Graph orientation to maximize the minimum weighted outdegree

DOI10.1142/S0129054111008246MaRDI QIDQ2997922zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmgraph orientationhardness of approximationmaximum flowscheduling

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Graph orientations optimizing the number of light or heavy vertices

Cites work

• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
• Beyond the flow decomposition barrier
• Complexity of automaton identification from given data
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Handbook of Graph Theory
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimizing maximum indegree
• Planar Formulae and Their Uses
• The Recognition of Series Parallel Digraphs

Cited in

(10)

• Graph balancing: a special case of scheduling unrelated parallel machines
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Graph orientation with edge modifications
• Graph orientation with splits
• Graph orientation with splits
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Truthful allocation in graphs and hypergraphs

This page was built for publication: Graph orientation to maximize the minimum weighted outdegree

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