Extremities and orderings defined by generalized graph search algorithms

DOI10.1016/J.ENDM.2005.06.066MaRDI QIDQ3439374zbMATH OpenOpenAlexFDO

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

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2005.06.066

zbMATH Keywords

graph searchLEX MLexBFSMCSmeominimal separatormoplexpeo

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Graph extremities defined by search algorithms
• Graph-Theoretic Concepts in Computer Science
• Maximal label search algorithms to compute perfect and minimal elimination orderings
• A Unified View of Graph Searching
• Computing a clique tree with the algorithm maximal label search

Cites work

• A Unified View of Graph Searching
• Graph-Theoretic Concepts in Computer Science
• Maximum cardinality search for computing minimal triangulations of graphs
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Moplex elimination orderings
• Separability generalizes Dirac's theorem
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Some aspects of perfect elimination orderings in chordal graphs

Cited in

(5)

• Graph extremities defined by search algorithms
• Computing a clique tree with the algorithm maximal label search
• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Graph-Theoretic Concepts in Computer Science
• Graphs with at most two moplexes

This page was built for publication: Extremities and orderings defined by generalized graph search algorithms

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