On end-vertices of lexicographic breadth first searches

DOI10.1016/j.dam.2009.10.001zbMath1225.05229OpenAlexW2086423153MaRDI QIDQ968161

Jean-Marc Lanlignel, Ekkehard Köhler, Derek Gordon Corneil

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.10.001

zbMATH Keywords

complexitygraph algorithmchordal graphsAT-free graphscocomparability graphsinterval graphssimplicial vertexgraph classeslexicographic breadth first search

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Recognizing graph search trees ⋮ Graph searches and their end vertices ⋮ End-Vertices of Graph Search Algorithms ⋮ Linearizing partial search orders ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ End vertices of graph searches on bipartite graphs ⋮ End-vertices of LBFS of (AT-free) bigraphs ⋮ The Recognition Problem of Graph Search Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Almost diameter of a house-hole-free graph in linear time via LexBFS
• LexBFS-orderings and powers of chordal graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Domination on Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• A Unified View of Graph Searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Graph-Theoretic Concepts in Computer Science
• Diameter determination on restricted graph families

This page was built for publication: On end-vertices of lexicographic breadth first searches