GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE

DOI10.1142/S0129054107004644MaRDI QIDQ3434271zbMATHOpenAlexFDO

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

Publication date 25 April 2007

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

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

zbMATH Keywords

approximation algorithmsgraph orientationNP-hardnessmin-max optimization

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
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted 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

Cites work

• scientific article; zbMATH DE number 5345854 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• A combinatorial theorem in plane geometry
• Approximation algorithms for scheduling unrelated parallel machines
• Complexity of approximating the oriented diameter of chordal graphs
• Diameter-preserving orientations of the torus
• Distances in orientations of graphs
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Minimizing maximum indegree
• Network Flow and Testing Graph Connectivity
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Strongly connected orientations of mixed multigraphs

Cited in

(25)

• A constructive arboricity approximation scheme
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• On finding orientations with the fewest number of vertices with small out-degree
• A fully asynchronous and fault tolerant distributed algorithm to compute a minimum graph orientation
• Literal Selection in Switching Lattice Design
• Density decompositions of networks
• A note on graph balancing problems with restrictions
• Graph balancing: a special case of scheduling unrelated parallel machines
• Laplacian energy of digraphs and a minimum Laplacian energy algorithm
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
• Parameterized orientable deletion
• Parameterized orientable deletion
• Graph orientation with edge modifications
• Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Upper and lower degree-constrained graph orientation with minimum penalty
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• Edge partitions of optimal 2-plane and 3-plane graphs
• The complexity of the proper orientation number
• Graph orientation with splits
• Graph orientation to maximize the minimum weighted outdegree
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• Graph orientation with splits

This page was built for publication: GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE

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