Distributed approximation algorithms for planar graphs

Andrzej Czygrinow; Michal Hańćkowiak; Edyta Szymańska

doi:10.1007/11758471_29

Distributed approximation algorithms for planar graphs

Andrzej Czygrinow, Michal Hańćkowiak, Edyta Szymańska

Mathematical and Statistical Sciences, School of (SoMSS)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

In this paper we construct two distributed algorithms for computing approximations of a largest matching and a minimum dominating set in planar graphs on n vertices. The approximation ratio in both cases approaches one with n tending to infinity and the number of synchronous communication rounds is poly-logarithmic in n. Our algorithms are purely deterministic.

Original language	English (US)
Title of host publication	Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings
Publisher	Springer Verlag
Pages	296-307
Number of pages	12
ISBN (Print)	354034375X, 9783540343752
DOIs	https://doi.org/10.1007/11758471_29
State	Published - 2006
Event	6th Italian Conference on Algorithms and Complexity, CIAC 2006 - Rome, Italy Duration: May 29 2006 → May 31 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3998 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	6th Italian Conference on Algorithms and Complexity, CIAC 2006
Country/Territory	Italy
City	Rome
Period	5/29/06 → 5/31/06

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11758471_29

Cite this

Czygrinow, A., Hańćkowiak, M., & Szymańska, E. (2006). Distributed approximation algorithms for planar graphs. In Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings (pp. 296-307). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3998 LNCS). Springer Verlag. https://doi.org/10.1007/11758471_29

Distributed approximation algorithms for planar graphs. / Czygrinow, Andrzej; Hańćkowiak, Michal; Szymańska, Edyta.
Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Verlag, 2006. p. 296-307 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3998 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Czygrinow, A, Hańćkowiak, M & Szymańska, E 2006, Distributed approximation algorithms for planar graphs. in Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3998 LNCS, Springer Verlag, pp. 296-307, 6th Italian Conference on Algorithms and Complexity, CIAC 2006, Rome, Italy, 5/29/06. https://doi.org/10.1007/11758471_29

Czygrinow A, Hańćkowiak M, Szymańska E. Distributed approximation algorithms for planar graphs. In Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Verlag. 2006. p. 296-307. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11758471_29

@inproceedings{3bf02897042345c28525916d884aeb32,

title = "Distributed approximation algorithms for planar graphs",

abstract = "In this paper we construct two distributed algorithms for computing approximations of a largest matching and a minimum dominating set in planar graphs on n vertices. The approximation ratio in both cases approaches one with n tending to infinity and the number of synchronous communication rounds is poly-logarithmic in n. Our algorithms are purely deterministic.",

author = "Andrzej Czygrinow and Michal Ha{\'n}{\'c}kowiak and Edyta Szyma{\'n}ska",

year = "2006",

doi = "10.1007/11758471_29",

language = "English (US)",

isbn = "354034375X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "296--307",

booktitle = "Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings",

note = "6th Italian Conference on Algorithms and Complexity, CIAC 2006 ; Conference date: 29-05-2006 Through 31-05-2006",

}

TY - GEN

T1 - Distributed approximation algorithms for planar graphs

AU - Czygrinow, Andrzej

AU - Hańćkowiak, Michal

AU - Szymańska, Edyta

PY - 2006

Y1 - 2006

N2 - In this paper we construct two distributed algorithms for computing approximations of a largest matching and a minimum dominating set in planar graphs on n vertices. The approximation ratio in both cases approaches one with n tending to infinity and the number of synchronous communication rounds is poly-logarithmic in n. Our algorithms are purely deterministic.

AB - In this paper we construct two distributed algorithms for computing approximations of a largest matching and a minimum dominating set in planar graphs on n vertices. The approximation ratio in both cases approaches one with n tending to infinity and the number of synchronous communication rounds is poly-logarithmic in n. Our algorithms are purely deterministic.

UR - http://www.scopus.com/inward/record.url?scp=33746043752&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746043752&partnerID=8YFLogxK

U2 - 10.1007/11758471_29

DO - 10.1007/11758471_29

M3 - Conference contribution

AN - SCOPUS:33746043752

SN - 354034375X

SN - 9783540343752

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 296

EP - 307

BT - Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings

PB - Springer Verlag

T2 - 6th Italian Conference on Algorithms and Complexity, CIAC 2006

Y2 - 29 May 2006 through 31 May 2006

ER -

Distributed approximation algorithms for planar graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this