✦ LIBER ✦

An optimal parallel algorithm for node ranking of cographs

✍ Scribed by Liu Chuan-Ming; Yu Ming-Shing

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 885 KB
Volume: 87
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(98)00056-0

No coin nor oath required. For personal study only.

✦ Synopsis

A ranking of a graph G is a mapping, p, from the vertices of G to the natural numbers such that for every path between any two vertices u and u, uf II, with p(u) = p(u), there exists at least one vertex w on that path with p(w) > p(u) = p(u). The value p(u) of a vertex u is the rank of vertex II. A ranking is optimal if the largest rank assigned is the smallest among all rankings. The optimal ranking problem on a graph G is the problem of finding an optimal ranking on G.

We persent a parallel algorithm which needs O(log n) time and n/ log n processors on the EREW PRAM model for this problem on cographs.

📜 SIMILAR VOLUMES

An Optimal Parallel Matching Algorithm f

An Optimal Parallel Matching Algorithm for Cographs

✍ R. Lin; S. Olariu 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 865 KB

The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. We show that the problem of finding a maximum matching in a cograph can be solved optimally in parallel by reducing it to parenthesis matching. With an \(n\)-v

An optimal path cover algorithm for cogr

An optimal path cover algorithm for cographs

✍ R. Lin; S. Olariu; G. Pruesse 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 512 KB

An optimal parallel algorithm for genera

An optimal parallel algorithm for generating combinations

✍ Selim G. Akl; David Gries; Ivan Stojmenovic 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 675 KB

An optimal parallel algorithm for mergin

An optimal parallel algorithm for merging using multiselection

✍ Narsingh Deo; Amit Jain; Muralidhar Medidi 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 654 KB

An optimal parallel algorithm for digita

An optimal parallel algorithm for digital curve segmentation

✍ Peter Damaschke 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 935 KB

First we give an optimal EREW PRAM algorithm that finds an unknown discrete monotone function f, with domain and range of size n, in O(log n) time using O(n) independent threshold queries of kind "f(x) > y?". Here "independent" means that simultaneous queries always refer to mutually disjoint values

An Optimal Shortest Path Parallel Algori

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs

✍ O.H. Ibarra; Q. Zheng 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 512 KB

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in \(O(\log n)\) time using \(O(n / \log n)\) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be f