Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
From MaRDI portal
Publication:5459150
DOI10.1007/11940128_56zbMath1135.68642WikidataQ57259024 ScholiaQ57259024MaRDI QIDQ5459150
Publication date: 24 April 2008
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11940128_56
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
05C20: Directed graphs (digraphs), tournaments
Related Items
On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition, Degree-constrained graph orientation: maximum satisfaction and minimum violation, Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree, Improved induced matchings in sparse graphs, Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree, The complexity of the proper orientation number, \((k,p)\)-planarity: a relaxation of hybrid planarity, Single-pass streaming algorithms to partition graphs into few forests, A Constructive Arboricity Approximation Scheme, Improved Induced Matchings in Sparse Graphs