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

DOI10.1016/J.DAM.2017.02.027zbMATH Open1361.05130arXiv1509.01307OpenAlexW2963191201MaRDI QIDQ528559FDOQ528559

Authors: J. Gorzny, Jing Huang 

Publication date: 12 May 2017

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

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.

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

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

zbMATH Keywords

bipartite graphcharacterizationend-vertexAT-freelexicographic breadth first searchproper interval bigraph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• Diameter determination on restricted graph families
• End-vertices of graph search algorithms
• Representation of a finite graph by a set of intervals on the real line
• Algorithmic Aspects of Vertex Elimination on Graphs
• Title not available (Why is that?)
• Representation characterizations of chordal bipartite graphs
• The LBFS structure and recognition of interval graphs
• Interval bigraphs and circular arc graphs
• Graph-Theoretic Concepts in Computer Science
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Graph extremities defined by search algorithms
• A Unified View of Graph Searching
• LexBFS-orderings and powers of chordal graphs
• Almost diameter of a house-hole-free graph in linear time via LexBFS
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Influence of the tie-break rule on the end-vertex problem
• On end-vertices of lexicographic breadth first searches

Cited In (9)

• Recognizing LBFS trees of bipartite graphs
• On end-vertices of lexicographic breadth first searches
• Title not available (Why is that?)
• The diameter of AT‐free graphs
• End-vertices of graph search algorithms
• Linearizing partial search orders
• On the end-vertex problem of graph searches
• End vertices of graph searches on bipartite graphs
• Graph Search Trees and Their Leaves

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)