Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree

DOI10.1007/978-3-540-72870-2_16MaRDI QIDQ5434435zbMATH OpenOpenAlexFDO

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

Publication date 4 January 2008

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72870-2_16

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Graph orientation to maximize the minimum weighted outdegree
• Graph orientations optimizing the number of light or heavy vertices
• Graph orientations optimizing the number of light or heavy vertices

Cited in

(24)

• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Upper and lower degree-constrained graph orientation with minimum penalty
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• Graph orientation with edge modifications
• Parameterized resiliency problems
• Graph balancing: a special case of scheduling unrelated parallel machines
• The edge-orientation problem and some of its variants on weighted graphs
• Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks
• From Graph Orientation to the Unweighted Maximum Cut
• Graph orientation to maximize the minimum weighted outdegree
• On the most imbalanced orientation of a graph
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Orientations of graphs with prescribed weighted out-degrees
• On finding orientations with the fewest number of vertices with small out-degree
• Parameterized resiliency problems via integer linear programming
• Approximating upper degree-constrained partial orientations
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
• 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
• On the most imbalanced orientation of a graph
• A note on graph balancing problems with restrictions

This page was built for publication: Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree

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