Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Kowalik, Lukasz

dblp



Editor(s):

Asano, Tetsuo

dblp

Not MPII Editor(s):

Asano, Tetsuo

BibTeX cite key*:

KowalikISAAC2006

Title, Booktitle

Title*:

Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures

Booktitle*:

Algorithms and Computation : 17th International Symposium, ISAAC 2006

Event, URLs

URL of the conference:

http://www.isical.ac.in/~isaac06/

URL for downloading the paper:

http://www.mimuw.edu.pl/~kowalik/papers/
http://www.springerlink.com/content/x3v4788k526751l1/fulltext.pdf

Event Address*:

Kolkata, India

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

18 December 2006

Event End Date:

20 December 2006

Publisher

Name*:

Springer

URL:

http://www.springer.com/

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

4288

Number:


Month:


Pages:

557-566

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

978-3-540-49694-6

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) 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).

URL for the Abstract:

http://www.springerlink.com/content/x3v4788k526751l1/



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{KowalikISAAC2006,
AUTHOR = {Kowalik, Lukasz},
EDITOR = {Asano, Tetsuo},
TITLE = {Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures},
BOOKTITLE = {Algorithms and Computation : 17th International Symposium, ISAAC 2006},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4288},
PAGES = {557--566},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Kolkata, India},
ISBN = {978-3-540-49694-6},
}


Entry last modified by Uwe Brahm, 04/25/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Lukasz Kowalik
Created
12/02/2006 12:25:29 AM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Regina Kraemer
Christine Kiesel
Lukasz Kowalik
Edit Dates
04/25/2007 10:34:58 AM
04/11/2007 11:10:20 AM
07.02.2007 16:05:56
2006-12-02 00:25:29
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section