A hybrid graph representation for recursive backtracking algorithms

DOI10.1007/978-3-642-14553-7_15MaRDI QIDQ3587345zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam, Michael A. Langston, Amer E. Mouawad, Clinton P. Nolan

Publication date 7 September 2010

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14553-7_15

zbMATH Keywords

data structuresdominating setexact algorithmsrecursive backtrackingvertex cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Automated generation of search tree algorithms for graph modification problems
• Representation of graphs and its algorithms based on BDD
• Accelerating backtrack search with a best-first-search strategy
• A theoretical analysis of backtracking in the graph coloring problem
• A theoretical evaluation of selected backtracking algorithms.

Cited in

(5)

• Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis
• scientific article; zbMATH DE number 3861209 (Why is no real title available?)
• SAT solving using XOR-OR-AND normal forms.
• Faster graph algorithms through DAG compression
• A backtracking algorithm for solving the nearly equitable strong edge-coloring problem on transportation network

This page was built for publication: A hybrid graph representation for recursive backtracking algorithms

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