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):

Fomin, Fedor V.

dblp

Not MPII Editor(s):

Fomin, Fedor V.

BibTeX cite key*:

Kowalik2005

Title, Booktitle

Title*:

Improved Edge Coloring with Three Colors

Booktitle*:

Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006

Event, URLs

URL of the conference:

http://www.ii.uib.no/wg06/

URL for downloading the paper:

http://www.mimuw.edu.pl/~kowalik/papers/

Event Address*:

Bergen, Norway

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

22 June 2006

Event End Date:

24 June 2006

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

4271

Number:


Month:


Pages:

90-101

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

3-540-48381-0

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We show an $O(1.344^n) = O(2^{0.427n})$ algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous, $O(2^{n/2})$ algorithm of Beigel and Eppstein. We apply a very natural approach of generating inclusion-maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique.

URL for the Abstract:

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



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{Kowalik2005,
AUTHOR = {Kowalik, Lukasz},
EDITOR = {Fomin, Fedor V.},
TITLE = {Improved Edge Coloring with Three Colors},
BOOKTITLE = {Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4271},
PAGES = {90--101},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Bergen, Norway},
ISBN = {3-540-48381-0},
}


Entry last modified by Uwe Brahm, 04/26/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:16:20 AM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Lukasz Kowalik
Lukasz Kowalik
Christine Kiesel
Christine Kiesel
Edit Dates
2007-04-26 18:55:45
2007-03-13 16:40:06
2007-03-13 16:05:24
07.02.2007 16:13:39
2006-12-02 00:16:20
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section