Unrestricted and complete breadth-first search of trapezoid graphs in O(n) time

DOI10.1016/J.IPL.2010.03.015MaRDI QIDQ763538zbMATH OpenOpenAlexWikidataFDO

Authors Christophe Crespelle, Philippe Gambette

Publication date 12 March 2012

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

Full work available at URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-00469844/file/2010CrespelleGambette.pdf

zbMATH Keywords

shortest pathsgraph algorithmsinterval graphspermutation graphstrapezoid graphsBFS treebreadth-first search (BFS)

Mathematics Subject Classification ID

Applications of graph theory (05C90) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 1960881
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• Parallel breadth-first search algorithms for trees and graphs
• Recognizing breadth-first search trees in linear time

Cites work

• scientific article; zbMATH DE number 432839 (Why is no real title available?)
• scientific article; zbMATH DE number 2044927 (Why is no real title available?)
• A faster algorithm for betweenness centrality*
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• Algorithmic graph theory and perfect graphs
• An efficient algorithm to find next-to-shortest path on trapezoid graphs
• An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Finding biconnected components in O(n) time for a class of graphs

Cited in

(3)

• Efficient algorithm for the vertex connectivity of trapezoid graphs
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• scientific article; zbMATH DE number 1960881 (Why is no real title available?)

This page was built for publication: Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q763538)