Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

DOI10.1016/j.dam.2010.11.003zbMath1210.05161OpenAlexW2138118431MaRDI QIDQ716177

Hirotaka Ono, Yuichi Asahiro, Eiji Miyano

Publication date: 19 April 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2324/25472

zbMATH Keywords

min-max optimizationgraph orientationcactusseries-parallel(outer)planar\((P_{4}-)\)bipartite\(\mathcal {NP}\)-hardness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Signed and weighted graphs (05C22)

Related Items

Weighted proper orientations of trees and graphs of bounded treewidth, On the Most Imbalanced Orientation of a Graph, Parameterized orientable deletion, Structural parameters for scheduling with assignment restrictions, Graph balancing: a special case of scheduling unrelated parallel machines, The complexity of the proper orientation number, Monadic Second Order Logic on Graphs with Local Cardinality Constraints, A note on graph balancing problems with restrictions, On the most imbalanced orientation of a graph, Complexity of secure sets, Graph orientation with splits, Exploring the gap between treedepth and vertex cover through vertex integrity, Unnamed Item, Exploring the gap between treedepth and vertex cover through vertex integrity, Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments, Graph Orientation with Edge Modifications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• Approximation algorithms for scheduling unrelated parallel machines
• Graph minors. III. Planar tree-width
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• A combinatorial theorem in plane geometry
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Minimizing maximum indegree
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Monadic Second Order Logic on Graphs with Local Cardinality Constraints
• Planar Formulae and Their Uses
• The Recognition of Series Parallel Digraphs
• Efficient Planarity Testing
• Handbook of Graph Theory
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computing Nash equilibria for scheduling on restricted parallel links