Reverse-search algorithm

<p>Reverse-search algorithms are a class of <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> for generating all objects of a given size, from certain classes of <a href="/facts/Combinatorics/k14xUoKT">combinatorial objects</a>. In many cases, these methods allow the objects to be generated in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> per object, using only enough memory to store a constant number of objects (<a href="/facts/Polynomial_space/RIkAClvG">polynomial space</a>). (Generally, however, they are not classed as polynomial-time algorithms, because the number of objects they generate is exponential.) They work by organizing the objects to be generated into a <a href="/facts/Spanning_tree/qQPN9taR">spanning tree</a> of their <a href="/facts/State_space/H1vjb3LL">state space</a>, and then performing a <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a> of this tree.
</p><p>Reverse-search algorithms were introduced by <a href="/facts/David_Avis/ofybefml">David Avis</a> and <a href="/facts/Komei_Fukuda/H88HI0Q4">Komei Fukuda</a> in 1991, for problems of generating the <a href="/facts/Vertex_(geometry)/ID3cea9z">vertices</a> of <a href="/facts/Convex_polytope/2pRHcRgC">convex polytopes</a> and the cells of <a href="/facts/Arrangement_of_hyperplanes/78c23rYy">arrangements of hyperplanes</a>. They were formalized more broadly by Avis and Fukuda in 1996.
</p>

Reverse-search algorithm open-in-new

Reverse-search algorithm