An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

Xin He

doi:10.1007/BF01189069

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

Xin He

Department of Computer Science and Engineering

University at Buffalo

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

9 Scopus citations

Abstract

We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takes O(log²n) time with O(n) processors on a CRCW PRAM, where n is the number of vertices of the graph.

Original language	English
Pages (from-to)	553-572
Number of pages	20
Journal	Algorithmica
Volume	13
Issue number	6
DOIs	https://doi.org/10.1007/BF01189069
State	Published - Jun 1995

Keywords

Parallel algorithms
Plane graphs
Rectangular duals

Access to Document

10.1007/BF01189069

Cite this

@article{6d6e752c2a4f4419bbc742e958623e37,

title = "An efficient parallel algorithm for finding rectangular duals of plane triangular graphs",

abstract = "We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takes O(log2n) time with O(n) processors on a CRCW PRAM, where n is the number of vertices of the graph.",

keywords = "Parallel algorithms, Plane graphs, Rectangular duals",

author = "Xin He",

year = "1995",

month = jun,

doi = "10.1007/BF01189069",

language = "English",

volume = "13",

pages = "553--572",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "6",

}

TY - JOUR

T1 - An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

AU - He, Xin

PY - 1995/6

Y1 - 1995/6

N2 - We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takes O(log2n) time with O(n) processors on a CRCW PRAM, where n is the number of vertices of the graph.

AB - We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takes O(log2n) time with O(n) processors on a CRCW PRAM, where n is the number of vertices of the graph.

KW - Parallel algorithms

KW - Plane graphs

KW - Rectangular duals

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

U2 - 10.1007/BF01189069

DO - 10.1007/BF01189069

M3 - Article

SN - 0178-4617

VL - 13

SP - 553

EP - 572

JO - Algorithmica

JF - Algorithmica

IS - 6

ER -

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this