Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time
type: Item
instance of: scholarly article
title: Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time
zbMATH Open document ID: 1233.05189
author: Christophe Crespelle
author: Philippe Gambette
published in: Information Processing Letters
publication date: 2012-03-12T00:00:00Z
full work available at URL: 2010CrespelleGambette.pdf
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6013742
zbMATH Keywords: breadth-first search (BFS)
zbMATH Keywords: trapezoid graphs
zbMATH Keywords: permutation graphs
zbMATH Keywords: interval graphs
zbMATH Keywords: shortest paths
zbMATH Keywords: graph algorithms
zbMATH Keywords: BFS tree
MaRDI profile type: Publication
OpenAlex ID: W2070696911
Wikidata QID: Q58172968
cites work: Q3639634
cites work: A faster algorithm for betweenness centrality*
cites work: An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
cites work: A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
cites work: Q4448751
cites work: Algorithmic graph theory and perfect graphs
cites work: Finding biconnected components in O(n) time for a class of graphs
cites work: Q3138973
cites work: Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
DOI: 10.1016/J.IPL.2010.03.015
description: scientific article; zbMATH DE number 6013742