Tree Size by Partial Backtracking

DOI10.1137/0207038MaRDI QIDQ4167574zbMATH OpenOpenAlexFDO

Authors Paul Walton jun. Purdom

Publication date 1978

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0207038

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Cited in

(11)

• Backtracking with multi-level dynamic search rearrangement
• Additive weights of a special class of nonuniformly distributed backtrack trees
• Probabilistic prediction of the complexity of traveling salesman problems based on approximating the complexity distribution from experimental data
• Completeness, approximability and exponential time results for counting problems with easy decision version
• On the average number of registers needed to evaluate a special class of backtrack trees
• Constraint bipartite vertex cover: simpler exact algorithms and implementations
• Uniformly growing backtrack trees
• Estimating the Size of Branch-and-Bound Trees
• Stochastic enumeration method for counting trees
• Determining if (FC-) (conflict-directed) backjumping visits a given node is NP-hard
• On the power of counting the total number of computation paths of NPTMs

This page was built for publication: Tree Size by Partial Backtracking

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