# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures

##### External Ressource

No external resources are shared

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Kowalik, L. (2006). Approximation Scheme for Lowest Outdegree Orientation and Graph
Density Measures. In *Algorithms and Computation: 17th International Symposium, ISAAC 2006*
(pp. 557-566). Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2219-4

##### Abstract

We deal with the problem of finding such an orientation of a given
graph that the largest number of edges leaving a vertex
(called the outdegree of the orientation) is small.
For any $\varepsilon\in(0,1)$ we show an $\tilde{O}(|E(G)|/\varepsilon)$
time algorithm which finds an orientation of an input graph $G$ with outdegree
at most $\lceil(1+\varepsilon)d^*\rceil$, where $d^*$ is the
maximum density of a subgraph of $G$. It is known that the optimal value of
orientation outdegree is $\lceil d^* \rceil$.
Our algorithm has applications in constructing labeling schemes,
introduced by Kannan et al. and in approximating such
graph density measures as arboricity, pseudoarboricity and maximum density.
Our results improve over the previous, 2-approximation algorithms
by Aichholzer et al. (for orientation / pseudoarboricity), by Arikati et al.
(for arboricity) and by Charikar (for maximum density).