A general label search to investigate classical graph search algorithms

DOI10.1016/J.DAM.2010.02.011MaRDI QIDQ617648zbMATH OpenOpenAlexFDO

Authors R. Krueger, Anne Berry, Geneviève Simonet

Publication date 21 January 2011

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

Full work available at URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-00565874/file/publiGLS.pdf

zbMATH Keywords

breadth first searchdepth first searchgraph labeling algorithmgraph search algorithmLexBFS

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Searching and sorting (68P10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• A novel labeling algorithm on several classes of graphs
• scientific article; zbMATH DE number 1538872
• A Unified View of Graph Searching
• scientific article; zbMATH DE number 139778
• Search problems on graphs
• A general heuristic bottom-up procedure for searching AND/OR graphs
• A study of graph labeling on a class of graphs
• Algorithms for searching explicit AND/OR graphs and their applications to problem reduction search
• scientific article; zbMATH DE number 5178701

Cites work

• scientific article; zbMATH DE number 1753166 (Why is no real title available?)
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A Unified View of Graph Searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• Depth-First Search and Linear Graph Algorithms
• Design and implementation of an efficient priority queue
• Graph-Theoretic Concepts in Computer Science
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• LexBFS-orderings and powers of chordal graphs
• Maximal label search algorithms to compute perfect and minimal elimination orderings
• On the semi-perfect elimination
• Preserving order in a forest in less than logarithmic time and linear space
• 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

(8)

• Organizing the atoms of the clique separator decomposition into an atom tree
• On the recognition of search trees generated by BFS and DFS
• Linearizing partial search orders
• Computing a clique tree with the algorithm maximal label search
• A tie-break model for graph search
• Graph Search Trees and Their Leaves
• A Unified View of Graph Searching
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS

This page was built for publication: A general label search to investigate classical graph search algorithms

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