On end-vertices of lexicographic breadth first searches

DOI10.1016/J.DAM.2009.10.001MaRDI QIDQ968161zbMATH OpenOpenAlexFDO

Authors Ekkehard Köhler, Jean-Marc Lanlignel, Derek G. 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 algorithminterval graphssimplicial vertexchordal graphscocomparability graphsgraph classesAT-free graphslexicographic breadth first search

Mathematics Subject Classification ID

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

Recommendations

• Influence of the tie-break rule on the end-vertex problem
• End-vertices of LBFS of (AT-free) bigraphs
• End-vertices of graph search algorithms
• scientific article; zbMATH DE number 1305500
• Graph-Theoretic Concepts in Computer Science

Cites work

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

Cited in

(12)

• Graph searches and their end vertices
• Graph Search Trees and Their Leaves
• Influence of the tie-break rule on the end-vertex problem
• A tie-break model for graph search
• End-vertices of graph search algorithms
• Recognizing graph search trees
• End vertices of graph searches on bipartite graphs
• Graph-Theoretic Concepts in Computer Science
• Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
• Linearizing partial search orders
• The recognition problem of graph search trees
• End-vertices of LBFS of (AT-free) bigraphs

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

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