Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
From MaRDI portal
Publication:5459150
DOI10.1007/11940128_56zbMath1135.68642OpenAlexW1713583684WikidataQ57259024 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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items
\((k,p)\)-planarity: a relaxation of hybrid planarity, Improved induced matchings in sparse graphs, On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition, Single-pass streaming algorithms to partition graphs into few forests, The complexity of the proper orientation number, A Constructive Arboricity Approximation Scheme, 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, Improved Induced Matchings in Sparse Graphs, Degree-constrained graph orientation: maximum satisfaction and minimum violation