Graph orientation to maximize the minimum weighted outdegree

DOI10.1142/S0129054111008246MaRDI QIDQ2997922zbMATHOpenAlexFDO

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 algorithmschedulinggraph orientationmaximum flowhardness of approximation

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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
• Minimizing maximum indegree
• Planar Formulae and Their Uses
• The Recognition of Series Parallel Digraphs

Cited in

(9)

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

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)