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

DOI10.1016/J.DAM.2017.02.027MaRDI QIDQ528559zbMATH OpenOpenAlexFDO

Authors J. 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)

Abstract: Lexicographic Breadth First Search (LBFS) is one of fundamental graph search algorithms that has numerous applications, including recognition of graph classes, computation of graph parameters, and detection of certain graph structures. The well-known result of Rose, Tarjan and Lueker on the end-vertices of LBFS of chordal graphs has tempted researchers to study the end-vertices of LBFS of various classes of graphs, including chordal graphs, split graphs, interval graphs, and asteroidal triple-free (AT-free) graphs. In this paper we study the end-vertices of LBFS of bipartite graphs. We show that deciding whether a vertex of a bipartite graph is the end-vertex of an LBFS is an NP-complete problem. In contrast we characterize the end-vertices of LBFS of AT-free bipartite graphs. Our characterization implies that the problem of deciding whether a vertex of an AT-free bipartite graph is the end-vertex of an LBFS is solvable in polynomial time. Key words: Lexicographic breadth first search, end-vertex, bipartite graphs, AT-free, proper interval bigraph, characterization, algorithm.

Recommendations

• On end-vertices of lexicographic breadth first searches
• End vertices of graph searches on bipartite graphs
• scientific article; zbMATH DE number 1522927
• On the end-vertex problem of graph searches
• scientific article; zbMATH DE number 1305500

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1522927 (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
• End-vertices of graph search algorithms
• Graph Classes: A Survey
• Graph extremities defined by search algorithms
• Graph-Theoretic Concepts in Computer Science
• Influence of the tie-break rule on the end-vertex problem
• Interval bigraphs and circular arc graphs
• LexBFS-orderings and powers of chordal graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• On end-vertices of lexicographic breadth first searches
• Representation characterizations of chordal bipartite graphs
• Representation of a finite graph by a set of intervals on the real line
• The LBFS structure and recognition of interval graphs

Cited in

(9)

• Recognizing LBFS trees of bipartite graphs
• scientific article; zbMATH DE number 1522927 (Why is no real title available?)
• Graph Search Trees and Their Leaves
• End-vertices of graph search algorithms
• End vertices of graph searches on bipartite graphs
• Linearizing partial search orders
• On end-vertices of lexicographic breadth first searches
• On the end-vertex problem of graph searches
• The diameter of AT‐free graphs

This page was built for publication: End-vertices of LBFS of (AT-free) bigraphs

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