English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures

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.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-000F-2219-4 Version Permalink: http://hdl.handle.net/11858/00-001M-0000-000F-221B-F
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kowalik, Lukasz1, Author              
Asano, Tetsuo1, Editor              
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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).

Details

show
hide
Language(s): eng - English
 Dates: 2007-04-252006
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314645
Other: Local-ID: C1256428004B93B8-CA824324F72E753BC12572370080AD09-KowalikISAAC2006
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Kolkata, India
Start-/End Date: 2006-12-18

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms and Computation : 17th International Symposium, ISAAC 2006
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 557 - 566 Identifier: ISBN: 978-3-540-49694-6

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 4288 Sequence Number: - Start / End Page: - Identifier: -