Estimating the Efficiency of Backtrack Programs
From MaRDI portal
Publication:4051599
DOI10.2307/2005469zbMath0297.68037OpenAlexW4230870880MaRDI QIDQ4051599
Publication date: 1975
Published in: Mathematics of Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2005469
Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
Completeness Results for Counting Problems with Easy Decision ⋮ Generating Hamiltonian circuits without backtracking from errors ⋮ Polynomial-average-time satisfiability problems ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ Stratified sampling for the Ising model: A graph-theoretic approach ⋮ Network-based heuristics for constraint-satisfaction problems ⋮ Parallel consistent labeling algorithms ⋮ Approximating the permanent: A simple approach ⋮ SelfSplit parallelization for mixed-integer linear programming ⋮ A note on extending Knuth's tree estimator to directed acyclic graphs ⋮ On estimating workload in interval branch-and-bound global optimization algorithms ⋮ On the complexity of finding shortest variable disjunction branch-and-bound proofs ⋮ The Efficiency of an Algorithm of Integer Programming: A Probabilistic Analysis ⋮ Estimating the Size of Branch-and-Bound Trees ⋮ On learning and branching: a survey ⋮ Interval selection in the streaming model ⋮ Revisiting global constraint satisfaction ⋮ A Sequential Importance Sampling Algorithm for Counting Linear Extensions ⋮ Backtracking with multi-level dynamic search rearrangement ⋮ An algorithm for computing the automorphism group of a Hadamard matrix ⋮ Two backtrack algorithms for the ratio frequency intermodulation problem ⋮ Predicting optimal solution costs with bidirectional stratified sampling in regular search spaces ⋮ Holes of the Leech lattice and the projective models of K3 surfaces ⋮ Object-oriented backtracking ⋮ On the estimate of the size of a directed graph ⋮ Constraint bipartite vertex cover: simpler exact algorithms and implementations ⋮ Algorithm runtime prediction: methods \& evaluation ⋮ From feasibility to improvement to proof: three phases of solving mixed-integer programs ⋮ Stochastic enumeration with importance sampling ⋮ The Knuth-Bendix procedure for strings as a substitute for coset enumeration ⋮ Stochastic enumeration method for counting trees ⋮ On a smooth quartic surface containing 56 lines which is isomorphic as a \(K3\) surface to the Fermat quartic ⋮ Predicting optimal solution cost with conditional probabilities ⋮ Accelerating backtrack search with a best-first-search strategy ⋮ Determining if (FC-) (conflict-directed) backjumping visits a given node is NP-hard ⋮ Probabilistic prediction of the complexity of traveling salesman problems based on approximating the complexity distribution from experimental data ⋮ A PAC Approach to Application-Specific Algorithm Selection ⋮ Approximately Counting Embeddings into Random Graphs ⋮ The scalability analysis of a parallel tree search algorithm ⋮ Finding and counting permutations via CSPs ⋮ On the classification of APN functions up to dimension five ⋮ Estimating Sizes of Social Networks via Biased Sampling ⋮ A clique search problem and its application to machine scheduling ⋮ Unnamed Item ⋮ On the existence of an integer solution to the relaxed Weber problem for a tree network ⋮ Enumeration and construction of pandiagonal Latin squares of prime order ⋮ Minimal and almost minimal perfect hash function search with application to natural language lexicon design ⋮ A backtracking algorithm to generate all kernels of a directed graph ⋮ Dynamic variable ordering in graph based backjumping algorithms for csps ⋮ Estimating the number of vertices of a polyhedron ⋮ The nonexistence of code words of weight 16 in a projective plane of order 10
