A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs

Xin He

doi:10.1016/0304-3975(88)90106-5

A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs

Xin He

Department of Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

This paper presents an efficient parallel algorithm for constructing maximal independent set in planar graphs. The algorithm runs in O(log²n) time with O(n) processors on a PRAM and is within an O(log²n) factor of optimal. The best previously known algorithm for this problem takes O(log²n) time with O(n³) processors. The key subroutine of the algorithm is an O(logn) time, O(n) processor parallel algorithm for constructing a maximal independent set in a one-page planar graph. This subroutine may be of independent interest.

Original language	English
Pages (from-to)	33-47
Number of pages	15
Journal	Theoretical Computer Science
Volume	61
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(88)90106-5
State	Published - Oct 1988

Access to Document

10.1016/0304-3975(88)90106-5

Cite this

@article{f6c7419fb6f74734bd6e2d5d34631b6f,

title = "A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs",

abstract = "This paper presents an efficient parallel algorithm for constructing maximal independent set in planar graphs. The algorithm runs in O(log2n) time with O(n) processors on a PRAM and is within an O(log2n) factor of optimal. The best previously known algorithm for this problem takes O(log2n) time with O(n3) processors. The key subroutine of the algorithm is an O(logn) time, O(n) processor parallel algorithm for constructing a maximal independent set in a one-page planar graph. This subroutine may be of independent interest.",

author = "Xin He",

year = "1988",

month = oct,

doi = "10.1016/0304-3975(88)90106-5",

language = "English",

volume = "61",

pages = "33--47",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs

AU - He, Xin

PY - 1988/10

Y1 - 1988/10

N2 - This paper presents an efficient parallel algorithm for constructing maximal independent set in planar graphs. The algorithm runs in O(log2n) time with O(n) processors on a PRAM and is within an O(log2n) factor of optimal. The best previously known algorithm for this problem takes O(log2n) time with O(n3) processors. The key subroutine of the algorithm is an O(logn) time, O(n) processor parallel algorithm for constructing a maximal independent set in a one-page planar graph. This subroutine may be of independent interest.

AB - This paper presents an efficient parallel algorithm for constructing maximal independent set in planar graphs. The algorithm runs in O(log2n) time with O(n) processors on a PRAM and is within an O(log2n) factor of optimal. The best previously known algorithm for this problem takes O(log2n) time with O(n3) processors. The key subroutine of the algorithm is an O(logn) time, O(n) processor parallel algorithm for constructing a maximal independent set in a one-page planar graph. This subroutine may be of independent interest.

UR - https://www.scopus.com/pages/publications/0024092687

U2 - 10.1016/0304-3975(88)90106-5

DO - 10.1016/0304-3975(88)90106-5

M3 - Article

AN - SCOPUS:0024092687

SN - 0304-3975

VL - 61

SP - 33

EP - 47

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this