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

DOI10.1016/J.IPL.2010.03.015zbMATH Open1233.05189OpenAlexW2070696911WikidataQ58172968 ScholiaQ58172968MaRDI QIDQ763538FDOQ763538

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 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)

Cites Work

• Algorithmic graph theory and perfect graphs
• A faster algorithm for betweenness centrality*
• 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
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Efficient algorithm for the vertex connectivity of trapezoid graphs
• Title not available (Why is that?)
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs

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)