Fast RNC and NC algorithms for maximal path sets

Ryuhei Uehara; Zhi Zhong Chen; Xin He

doi:10.1016/S0304-3975(97)00132-1

Fast RNC and NC algorithms for maximal path sets

Ryuhei Uehara
, Zhi Zhong Chen
, Xin He

Department of Computer Science and Engineering

Tokyo Woman's Christian University
Tokyo Denki University

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

Abstract

We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log² n) time with O(Δ²(n + m)/log n) processors on an EREW PRAM. The results improve on the previous bests and can also be extended to digraphs. We then use the results to improve the time complexity of the best previous NC approximation algorithm for the shortest superstring problem.

Original language	English
Pages (from-to)	89-98
Number of pages	10
Journal	Theoretical Computer Science
Volume	215
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(97)00132-1
State	Published - Feb 28 1999

Keywords

Approximation algorithms
Graph algorithms
Maximal path sets
Parallel algorithms
Randomized parallel algorithms
Shortest common superstrings

Access to Document

10.1016/S0304-3975(97)00132-1

Cite this

@article{b13ee1697d064fde8c5e7173dd78db6f,

title = "Fast RNC and NC algorithms for maximal path sets",

abstract = "We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log2 n) time with O(Δ2(n + m)/log n) processors on an EREW PRAM. The results improve on the previous bests and can also be extended to digraphs. We then use the results to improve the time complexity of the best previous NC approximation algorithm for the shortest superstring problem.",

keywords = "Approximation algorithms, Graph algorithms, Maximal path sets, Parallel algorithms, Randomized parallel algorithms, Shortest common superstrings",

author = "Ryuhei Uehara and Chen, \{Zhi Zhong\} and Xin He",

year = "1999",

month = feb,

day = "28",

doi = "10.1016/S0304-3975(97)00132-1",

language = "English",

volume = "215",

pages = "89--98",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Fast RNC and NC algorithms for maximal path sets

AU - Uehara, Ryuhei

AU - Chen, Zhi Zhong

AU - He, Xin

PY - 1999/2/28

Y1 - 1999/2/28

N2 - We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log2 n) time with O(Δ2(n + m)/log n) processors on an EREW PRAM. The results improve on the previous bests and can also be extended to digraphs. We then use the results to improve the time complexity of the best previous NC approximation algorithm for the shortest superstring problem.

AB - We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log2 n) time with O(Δ2(n + m)/log n) processors on an EREW PRAM. The results improve on the previous bests and can also be extended to digraphs. We then use the results to improve the time complexity of the best previous NC approximation algorithm for the shortest superstring problem.

KW - Approximation algorithms

KW - Graph algorithms

KW - Maximal path sets

KW - Parallel algorithms

KW - Randomized parallel algorithms

KW - Shortest common superstrings

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

U2 - 10.1016/S0304-3975(97)00132-1

DO - 10.1016/S0304-3975(97)00132-1

M3 - Article

AN - SCOPUS:0345767268

SN - 0304-3975

VL - 215

SP - 89

EP - 98

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Fast RNC and NC algorithms for maximal path sets

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this