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

DOI10.1016/0020-0190(94)90053-1zbMath0787.68053OpenAlexW1967528652MaRDI QIDQ1313714

S. Lakshmivarahan, Y. Daniel Liang, Sudarshan K. Dhall, Chongkye Rhee

Publication date: 1994

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

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90053-1

zbMATH Keywords

depth-first search treepermutation graphbreadth-first search tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

A linear time algorithm for finding depth-first spanning trees on trapezoid graphs ⋮ An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs ⋮ Finding biconnected components in O(n) time for a class of graphs ⋮ An NC algorithm for the clique cover problem in cocomparability graphs and its application ⋮ Computation of diameter, radius and center of permutation graphs ⋮ Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs ⋮ Localized and compact data-structure for comparability graphs ⋮ Additive tree 2-spanners of permutation graphs ⋮ Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time ⋮ Shorter Labeling Schemes for Planar Graphs ⋮ Distance Labeling for Permutation Graphs

Cites Work

• Unnamed Item
• Preserving order in a forest in less than logarithmic time and linear space
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs