Graph extremities defined by search algorithms
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.
- Extremities and orderings defined by generalized graph search algorithms
- scientific article; zbMATH DE number 4174651
- scientific article; zbMATH DE number 4156240
- Graph searches and their end vertices
- Graph Searches and Their End Vertices.
- End-vertices of graph search algorithms
- scientific article; zbMATH DE number 815069
- Search problems on graphs
- scientific article; zbMATH DE number 861311
- Algorithms and complexity results for finding graphs with extremal Randić index
- A Unified View of Graph Searching
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Algorithmic Aspects of Vertex Elimination on Graphs
- Asteroidal Triple-Free Graphs
- Extremities and orderings defined by generalized graph search algorithms
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- Incidence matrices and interval 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
- Maximal label search algorithms to compute perfect and minimal elimination orderings
- Maximum cardinality search for computing minimal triangulations of graphs
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- On rigid circuit graphs
- Recognizing weakly triangulated graphs by edge separability
- Representation of a finite graph by a set of intervals on the real line
- Separability generalizes Dirac's theorem
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Triangulated graphs and the elimination process
- Computing a clique tree with the algorithm maximal label search
- A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- Graph searches and their end vertices
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- Moplex orderings generated by the LexDFs algorithm
- Extremities and orderings defined by generalized graph search algorithms
- Organizing the atoms of the clique separator decomposition into an atom tree
- scientific article; zbMATH DE number 861311 (Why is no real title available?)
- End-vertices of LBFS of (AT-free) bigraphs
- Computing and listing avoidable vertices and paths
- Computing and listing avoidable vertices and paths
- Graphs with at most two moplexes
- Growing trees and amoebas' replications
- Avoidability beyond paths
This page was built for publication: Graph extremities defined by search algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662546)
