Graph orientation to maximize the minimum weighted outdegree

DOI10.1142/S0129054111008246zbMATH Open1216.68114OpenAlexW2001855339MaRDI QIDQ2997922FDOQ2997922

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

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

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)

Cites Work

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

Cited In (9)

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

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)