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

(14)

• The complexity of the proper orientation number
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• \((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
• A simple greedy algorithm for dynamic graph orientation
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Improved induced matchings in sparse graphs
• Distributed dense subgraph detection and low outdegree orientation
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Edge-coloring sparse graphs with Colors in quasilinear time
• Engineering edge orientation algorithms
• Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism

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)