GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE

DOI10.1142/S0129054107004644zbMath1119.68223OpenAlexW2033433572MaRDI QIDQ3434271

Hirotaka Ono, Yuichi Asahiro, 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

min-max optimizationapproximation algorithmsNP-hardnessgraph orientation

Mathematics Subject Classification ID

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

Related Items

Parameterized orientable deletion, Laplacian Energy of Digraphs and a Minimum Laplacian Energy Algorithm, Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees, Literal Selection in Switching Lattice Design, Graph balancing: a special case of scheduling unrelated parallel machines, The complexity of the proper orientation number, A Constructive Arboricity Approximation Scheme, GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE, Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree, Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree, Edge partitions of optimal 2-plane and 3-plane graphs, A note on graph balancing problems with restrictions, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Unnamed Item, Upper and lower degree-constrained graph orientation with minimum penalty, Density decompositions of networks, Degree-constrained graph orientation: maximum satisfaction and minimum violation

Cites Work

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