de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44835

Kowalik,  Lukasz
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44035

Asano,  Tetsuo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2219-4
Zusammenfassung
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).