End-vertices of LBFS of (AT-free) bigraphs

DOI10.1016/j.dam.2017.02.027zbMath1361.05130arXiv1509.01307OpenAlexW2963191201MaRDI QIDQ528559

Jan Gorzny, Jing Huang

Publication date: 12 May 2017

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

Full work available at URL: https://arxiv.org/abs/1509.01307

zbMATH Keywords

bipartite graphcharacterizationend-vertexAT-freelexicographic breadth first searchproper interval bigraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items

Linearizing partial search orders, The diameter of AT‐free graphs, End vertices of graph searches on bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On end-vertices of lexicographic breadth first searches
• Almost diameter of a house-hole-free graph in linear time via LexBFS
• LexBFS-orderings and powers of chordal graphs
• Graph extremities defined by search algorithms
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Representation characterizations of chordal bipartite graphs
• End-Vertices of Graph Search Algorithms
• The LBFS Structure and Recognition of Interval 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
• Graph Classes: A Survey
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Interval bigraphs and circular arc graphs
• Graph-Theoretic Concepts in Computer Science
• Diameter determination on restricted graph families