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

DOI10.1016/S0020-0190(97)00088-4zbMath1336.05128OpenAlexW1979383396MaRDI QIDQ287118

Hon-Chan Chen, Yue-Li Wang

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00088-4

zbMATH Keywords

spanning treetrapezoid graphsdepth-first searchpermutation graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph ⋮ Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-processor algorithm for depth-first search in planar graphs
• Trapezoid graphs and their coloring
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Dominations in trapezoid graphs
• Parallel Depth-First Search in General Directed Graphs
• Planar Depth-First Search in $O(\log n)$ Parallel Time
• On the 2-Chain Subgraph Cover and Related Problems
• On the existence of special depth first search trees
• A new algorithm for minimum spanning tree using depth-first-search in an undirected graph
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: A linear time algorithm for finding depth-first spanning trees on trapezoid graphs