GASCHNIG, J Experimental case studies of backtrack vs Waltz-type vs new algor,thms for satlsficmg assignment problems. Proc. 2rid Nat Conf of the Canadxan Society for Computat,onal Studies of Intelligence, Toronto, Ontano, 1978, pp. 268-277

Google Scholar

[6]

KNUTH, D E. Estlmattng the efficiency of backtrack programs Math. Comput 29 (Jan 1975), 121-136.

Google Scholar

[7]

MACKWORTH, A.K Consistency in networks of relations Artif. Intell. 8 (1977), 99-118

Google Scholar

[8]

MATULA, D.W A ram-max theorem for graphs with apphcation to graph coloring SlAM Rev I0 (1968), 481-482

Google Scholar

[9]

MATULA, O W, MARBLE, G, Arid ISAACSON, J.D Graph coloring algorithms In Graph Theory and Computing, R C Read, Ed, Academtc Press, New York, 1972, pp 109-122

Google Scholar

[10]

NILSSON, N J. Problem-Solving Methods m Art~clai Intelligence McGraw-Hill, New York, 1971

Crossref

Google Scholar

[11]

PURDOM, P W.Tree size by partial backtracking. SIAM d. Comput 7 (1978), 481-491.

Google Scholar

[12]

SZEKERES, G., AND WILF, H S.Aa mequahty for the chromatic number of a graph J Comb Theory 4 (1968), 1-3.

Google Scholar

[13]

TENENBAUM, J M, AND BARROW, H.G IGS A paradigm for mtegraUng image segmentation and interpretation. In Pattern Recogmtton and Artificial lntelhgence, C.H. Chen, Ed. Academic Press, New York, 1976, pp 472-507

Google Scholar

[14]

WALTZ, D.L Understanding line drawmgs of scenes with shadows. In The Psychology of Computer Vision, P H Winston, Ed, McGraw-Hall, New York, 1975, pp 19-91.

Google Scholar

[15]

WELLS, M B. Elements of Combinatorial Computing Pergamon Press, New York, 1971.

Google Scholar

[16]

WIRTH.N Algorithms + Data Structures --- Programs Prentice-Hall, Englewood Cliffs, N J, 1976

Crossref

Google Scholar

Cited By

View all

Wang RWooldridge MDy JNatarajan S(2024)Encoding constraints as binary constraint networks satisfying BTPProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i8.28657(8172-8181)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i8.28657
Mao JLozano-Pérez TTenenbaum JKaelbling LOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)What planning problems can a relational neural network solve?Proceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668723(59522-59542)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668723
Xie ZWang XYang LPang LZhao XYang Y(2023)Convergence analysis of a survey propagation algorithmJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-22377945:6(9239-9252)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/JIFS-223779
Show More Cited By

Index Terms

A Sufficient Condition for Backtrack-Free Search
1. Information systems
  1. Information retrieval
    1. Information retrieval query processing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Backtracking

Recommendations

A sufficient condition for backtrack-bounded search

Backtrack search is often used to solve constraint satisfaction problems. A relationship involving the structure of the constraints is described that provides a bound on the backtracking required to advance deeper into the backtrack tree. This analysis ...
A new necessary and sufficient global optimality condition for canonical DC problems

The paper proposes a new necessary and sufficient global optimality condition for canonical DC optimization problems. We analyze the rationale behind Tuy's standard global optimality condition for canonical DC problems, which relies on the so-called ...
A Necessary and Sufficient Condition for Approachability

In the framework of two-person repeated games with vector payoffs, Blackwell defined the property of approachability and introduced a sufficient condition for it. He also proved that this condition is necessary in the case of convex sets.

We generalize ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 29, Issue 1

Jan. 1982

268 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322290

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1982

Published in JACM Volume 29, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

497
Total Citations
View Citations
1,537
Total Downloads

Downloads (Last 12 months)144
Downloads (Last 6 weeks)16

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang RWooldridge MDy JNatarajan S(2024)Encoding constraints as binary constraint networks satisfying BTPProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i8.28657(8172-8181)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i8.28657
Mao JLozano-Pérez TTenenbaum JKaelbling LOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)What planning problems can a relational neural network solve?Proceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668723(59522-59542)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668723
Xie ZWang XYang LPang LZhao XYang Y(2023)Convergence analysis of a survey propagation algorithmJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-22377945:6(9239-9252)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/JIFS-223779
Wang RYap RWilliams BChen YNeville J(2023)The expressive power of Ad-Hoc constraints for modelling CSPsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i4.25526(4104-4114)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i4.25526
Amano Y(2023)Locally defined independence systems on graphsDiscrete Applied Mathematics10.1016/j.dam.2022.11.001326(1-16)Online publication date: Feb-2023
https://doi.org/10.1016/j.dam.2022.11.001
Fan CLi PLi XKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Private graph all-pairwise-shortest-path distance release with improved error rateProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601567(17844-17856)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601567
Pearl J(2022)Fusion, Propagation, and Structuring in Belief NetworksProbabilistic and Causal Inference10.1145/3501714.3501728(139-188)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3501714.3501728
Carbonnel CRomero MŽivný S(2022)The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other SideSIAM Journal on Computing10.1137/19M125012151:1(19-69)Online publication date: 25-Jan-2022
https://doi.org/10.1137/19M1250121
Karahalios Avan Hoeve W(2022)Variable ordering for decision diagrams: A portfolio approachConstraints10.1007/s10601-021-09325-627:1-2(116-133)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s10601-021-09325-6
Dlask TWerner T(2022)Classes of linear programs solvable by coordinate-wise minimizationAnnals of Mathematics and Artificial Intelligence10.1007/s10472-021-09731-990:7-9(777-807)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s10472-021-09731-9
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

A sufficient condition for backtrack-bounded search

A new necessary and sufficient global optimality condition for canonical DC problems

A Necessary and Sufficient Condition for Approachability

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations