𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear time algorithm for finding depth-first spanning trees on trapezoid graphs

✍ Scribed by Hon-Chan Chen; Yue-Li Wang

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
458 KB
Volume
63
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a connected graph of n vertices and m edges. The problem of finding a depth-first spanning tree of G is to find a subgraph of G connecting the n vertices with n -1 edges by depth-first search. In this paper, we propose an O(n) time algorithm for solving this problem on trapezoid graphs. Our algorithm can also find depth-first spanning trees of permutation graphs in linear time, improving the recent algorithm on permutation graphs which takes O(n log log n) time.

πŸ“œ SIMILAR VOLUMES

A Linear Time Algorithm for Finding ak-T
A Linear Time Algorithm for Finding ak-Tree Core
✍ Akiyoshi Shioura; Takeaki Uno πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 173 KB

Given a tree containing n vertices, consider the sum of the distance between all Ε½ . vertices and a k-leaf subtree subtree which contains exactly k leaves . A k-tree core is a k-leaf subtree which minimizes the sum of the distances. In this paper, we propose a linear time algorithm for finding a k-t

A linear-time algorithm for connectedr-d
A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
✍ BrandstοΏ½dt, Andreas; Dragan, Feodor F. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 83 KB πŸ‘ 1 views

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree