๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Constructing the visibility graph for n-line segments in O(n2) time

โœ Scribed by Emo Welzl

Book ID
113162772
Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
393 KB
Volume
20
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Finding biconnected components in O(n) t
Finding biconnected components in O(n) time for a class of graphs
โœ Y.Daniel Liang; Chongkye Rhee ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 460 KB

A rooted tree is called a single-branch tree if there. is exactly one nonleaf vertex on each level except the bottom level of the tree. We present an O(n) time algorithm for finding biconnected components in a graph G, assuming that a single-branch breadth-first search (SBS) tree of any connected in

An O(n) time algorithm for maximum match
An O(n) time algorithm for maximum matching in P4-tidy graphs
โœ J.L. Fouquet; I. Parfenoff; H. Thuillier ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 630 KB

The A-tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with "few" induced P4 s. In this paper, we extend to PA-tidy graphs a linear time algorithm of C.-H. Yang and M.-S. Yu for finding a maximum matching in a cograph G (given a parse tree associated to G). @