Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
type: Item
instance of: scholarly article
title: Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
zbMATH Open document ID: 1210.05161
author: Yuichi Asahiro
author: Eiji Miyano
author: Hirotaka Ono
published in: Discrete Applied Mathematics
publication date: 2011-04-19T00:00:00Z
full work available at URL: http://hdl.handle.net/2324/25472
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C22
zbMATH DE Number: 5880187
zbMATH Keywords: graph orientation
zbMATH Keywords: min-max optimization
zbMATH Keywords: \(\mathcal {NP}\)-hardness
zbMATH Keywords: cactus
zbMATH Keywords: (outer)planar
zbMATH Keywords: \((P_{4}-)\)bipartite
zbMATH Keywords: series-parallel
MaRDI profile type: Publication
OpenAlex ID: W2138118431
cites work: Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
cites work: GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Q3024792
cites work: A combinatorial theorem in plane geometry
cites work: Computing Nash equilibria for scheduling on restricted parallel links
cites work: Q4198056
cites work: Handbook of Graph Theory
cites work: \(P_4\)-colorings and \(P_4\)-bipartite graphs
cites work: Efficient Planarity Testing
cites work: Finding and counting small induced subgraphs efficiently
cites work: Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
cites work: Approximation algorithms for scheduling unrelated parallel machines
cites work: Planar Formulae and Their Uses
cites work: Linear algorithms to recognize outerplanar and maximal outerplanar graphs
cites work: Q3799261
cites work: Graph minors. III. Planar tree-width
cites work: Q3330973
cites work: Polynomial time approximation algorithms for machine scheduling: Ten open problems
cites work: Monadic Second Order Logic on Graphs with Local Cardinality Constraints
cites work: The Recognition of Series Parallel Digraphs
cites work: Minimizing maximum indegree
DOI: 10.1016/J.DAM.2010.11.003
Recommended article: Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
Recommended article: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
Recommended article: GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE
Recommended article: Orientations of graphs with prescribed weighted out-degrees
Recommended article: Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
Recommended article: Degree-constrained orientation of maximum satisfaction: Graph classes and parameterized complexity
Recommended article: GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
Recommended article: ABOUT SOME CLASSES OF EXTREMAL ORIENTED GRAPHS
Recommended article: The edge-orientation problem and some of its variants on weighted graphs
Recommended article: The complexity of two graph orientation problems
description: scientific article; zbMATH DE number 5880187