Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
DOI10.1007/11940128_56zbMATH Open1135.68642OpenAlexW1713583684WikidataQ57259024 ScholiaQ57259024MaRDI QIDQ5459150FDOQ5459150
Authors: Łukasz Kowalik 
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
Recommendations
- Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- Fast Algorithms for Pseudoarboricity
- A simple greedy algorithm for dynamic graph orientation
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Cited In (12)
- Improved induced matchings in sparse graphs
- Degree-constrained graph orientation: maximum satisfaction and minimum violation
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- A constructive arboricity approximation scheme
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- Improved induced matchings in sparse graphs
- \((k,p)\)-planarity: a relaxation of hybrid planarity
- Single-pass streaming algorithms to partition graphs into few forests
- On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
- A simple greedy algorithm for dynamic graph orientation
- Distributed dense subgraph detection and low outdegree orientation
- The complexity of the proper orientation number
This page was built for publication: Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5459150)
