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

DOI10.1016/j.ipl.2010.03.015zbMath1233.05189OpenAlexW2070696911WikidataQ58172968 ScholiaQ58172968MaRDI QIDQ763538

Philippe Gambette, Christophe Crespelle

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 algorithmstrapezoid graphsinterval graphspermutation graphsBFS treebreadth-first search (BFS)

Mathematics Subject Classification ID

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

Related Items

Efficient algorithm for the vertex connectivity of trapezoid graphs

Cites Work

• 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
• 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
• Algorithmic graph theory and perfect graphs
• A faster algorithm for betweenness centrality*
• Unnamed Item
• Unnamed Item
• Unnamed Item