✦ LIBER ✦

Recognizing breadth-first search trees in linear time

✍ Scribed by Udi Manber

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 511 KB
Volume: 34
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(90)90155-q

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Efficient algorithms for finding depth-f

Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs

✍ C. Rhee; Y.Daniel Liang; S.K. Dhall; S. Lakshmivarahan 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 512 KB

An optimal EREW parallel algorithm for c

An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs

✍ H.S. Chao; F.R. Hsu; R.C.T. Lee 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 498 KB

Given a undirected graph G, the breadth-first search tree is constructed by a breadth-first search on G. In this paper, an optimal parallel algorithm is presented for constructing the breadth-first search tree for permutation graphs in O(log n) time by using O(n/Iog n) processors under the EREW PRAM

Breadth-first traversal of trees and int

Breadth-first traversal of trees and integer sorting in parallel

✍ Calvin C.-Y. Chen; Sajal K. Das 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 868 KB

New efficient breadth-first/level traver

New efficient breadth-first/level traversal tree search method for the design and upgrade of sensor networks

✍ Duy Quang Nguyen; Miguel J. Bagajewicz 📂 Article 📅 2010 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 427 KB 👁 2 views

## Abstract This work studies the problem of optimally locating sensors for monitoring chemical processes, formally known as the sensor network design and upgrade problem. This problem is an integer programming problem and has been solved to global optimality only using tree search methods using de

On Linear Time Minor Tests with Depth-Fi

On Linear Time Minor Tests with Depth-First Search

✍ H.L. Bodlaender 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 911 KB

Recent results on graph minors make it desirable to have efficient algorithms that, for a fixed set of graphs \(\left\{H_{1}, \ldots, H_{c}\right\}\), test whether a given graph \(G\) contains at least one graph \(H_{i}\) as a minor. In this paper we show the following result: if at least one graph

Recognizing Hamming graphs in linear tim

Recognizing Hamming graphs in linear time and space

✍ Wilfried Imrich; Sandi Klavžar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 417 KB

Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improves a previous algorithm which was linear in time but not in space. This also favorab