Graph extremities defined by search algorithms

DOI10.3390/a3020100zbMath1461.05202OpenAlexW2117033169MaRDI QIDQ1662546

Jean-Paul Bordat, Geneviève Simonet, Jean R. S. Blair, Anne Berry

Publication date: 20 August 2018

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a3020100

zbMATH Keywords

MCSgraph searchMLSLexBFSgraph extremity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Graph searches and their end vertices, Computing a clique tree with the algorithm maximal label search, Organizing the atoms of the clique separator decomposition into an atom tree, Computing and listing avoidable vertices and paths, Computing and listing avoidable vertices and paths, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, Moplex orderings generated by the LexDFs algorithm, End-vertices of LBFS of (AT-free) bigraphs, Avoidable vertices and edges in graphs: existence, characterization, and applications, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds

Cites Work

• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• LexBFS-orderings and powers of chordal graphs
• Separability generalizes Dirac's theorem
• Maximum cardinality search for computing minimal triangulations of graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Extremities and orderings defined by generalized graph search algorithms
• A Unified View of Graph Searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Asteroidal Triple-Free Graphs
• Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings
• A wide-range algorithm for minimal triangulation from an arbitrary ordering