Graph extremities defined by search algorithms
type: Item
instance of: scholarly article
title: Graph extremities defined by search algorithms
zbMATH Open document ID: 1461.05202
author: Anne Berry
author: Jean R. S. Blair
author: Jean-Paul Bordat
author: Geneviève Simonet
published in: Algorithms
publication date: 2018-08-20T00:00:00Z
review text: Summary: Graph search algorithms have exploited graph extremities, such as the leaves of a tree and the simplicial vertices of a chordal graph. Recently, several well-known graph search algorithms have been collectively expressed as two generic algorithms called MLS and MLSM. In this paper, we investigate the properties of the vertex that is numbered 1 by MLS on a chordal graph and by MLSM on an arbitrary graph. We explain how this vertex is an extremity of the graph. Moreover, we show the remarkable property that the minimal separators included in the neighborhood of this vertex are totally ordered by inclusion.
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6920515
zbMATH Keywords: graph search
zbMATH Keywords: graph extremity
zbMATH Keywords: LexBFS
zbMATH Keywords: MCS
zbMATH Keywords: MLS
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a3020100
OpenAlex ID: W2117033169
cites work: On rigid circuit graphs
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Incidence matrices and interval graphs
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Asteroidal Triple-Free Graphs
cites work: Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
cites work: LexBFS-orderings and powers of chordal graphs
cites work: LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
cites work: A Unified View of Graph Searching
cites work: Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings
cites work: Separability generalizes Dirac's theorem
cites work: Q4288578
cites work: Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
cites work: Maximum cardinality search for computing minimal triangulations of graphs
cites work: Recognizing weakly triangulated graphs by edge separability
cites work: A wide-range algorithm for minimal triangulation from an arbitrary ordering
cites work: Triangulated graphs and the elimination process
cites work: Extremities and orderings defined by generalized graph search algorithms
DOI: 10.3390/A3020100
Recommended article: Extremities and orderings defined by generalized graph search algorithms
Recommended article: Q3199182
Recommended article: Q3484665
Recommended article: Graph searches and their end vertices
Recommended article: Graph Searches and Their End Vertices.
Recommended article: End-Vertices of Graph Search Algorithms
Recommended article: Q4855405
Recommended article: Search problems on graphs
Recommended article: Q4871035
Recommended article: Algorithms and complexity results for finding graphs with extremal Randić index
description: scientific article; zbMATH DE number 6920515