Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures

DOI10.1007/11940128_56MaRDI QIDQ5459150zbMATH OpenOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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

Cited in

(11)

• 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
• 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)