DOI: 10.1016/0020-0255(90)90030-e. Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem

Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem

10.1016/0020-0255(90)90030-e

Crossref journal-article

Elsevier BV

Information Sciences (78)

Bibliography

Ming-Te, C., & Franco, J. (1990). Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem. Information Sciences, 51(3), 289â314.

Authors 2

Chao Ming-Te (first)
John Franco (additional)

References 11 Referenced 77

10.1137/0210043 / SIAM J. Comput. / An average time analysis of backtracking by Brown (1981)
{'key': '10.1016/0020-0255(90)90030-E_BIB2', 'article-title': 'Probabilistic Analysis and Performance Measurement of Algorithms for the Satisfiability Problem', 'author': 'Chao', 'year': '1984'} / Probabilistic Analysis and Performance Measurement of Algorithms for the Satisfiability Problem by Chao (1984)
10.1137/0215080 / SIAM J. Comput. / Probabilistic analysis of two heuristics for the 3-satisfiability problem by Chao (1986)
10.1145/321033.321034 / J. Assoc. Comput. Mach. / A computing procedure for quantification theory by Davis (1960)
{'key': '10.1016/0020-0255(90)90030-E_BIB5', 'series-title': 'Probabilistic Methods in Combinatorics', 'author': 'Erdos', 'year': '1974'} / Probabilistic Methods in Combinatorics by Erdos (1974)
10.1016/0020-0190(86)90051-7 / Inform. Process. Lett. / On the probabilistic performance of algorithms for the satisfiability problem by Franco (1986)
10.1016/0166-218X(83)90017-3 / Discrete Appl. Math. / Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem by Franco (1983)
{'key': '10.1016/0020-0255(90)90030-E_BIB8', 'series-title': 'Proceedings of the 4th Workshop on Automated Deduction', 'first-page': '1', 'article-title': 'Average case complexity of the satisfiability problem', 'author': 'Goldberg', 'year': '1979'} / Proceedings of the 4th Workshop on Automated Deduction / Average case complexity of the satisfiability problem by Goldberg (1979)
10.1016/0020-0190(82)90110-7 / Inform. Process. Lett. / Average time analysis of simplified Davis-Putnam procedures by Goldberg (1982)
10.1016/S0004-3702(83)80007-1 / Artificial Intelligence / Search rearrangement backtracking and polynomial average time by Purdom (1983)
10.1137/0214067 / SIAM J. Comput. / The pure literal rule and polynomial average time by Purdom (1985)

Dates

Type	When
Created	22 years, 1 month ago (June 30, 2003, 1:28 p.m.)
Deposited	6 years, 5 months ago (March 18, 2019, 9:22 a.m.)
Indexed	1 month, 1 week ago (July 13, 2025, 10:34 p.m.)
Issued	35 years ago (Aug. 1, 1990)
Published	35 years ago (Aug. 1, 1990)
Published Print	35 years ago (Aug. 1, 1990)

Funders 0

None

BibTeX

@article{Ming_Te_1990, title={Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem}, volume={51}, ISSN={0020-0255}, url={http://dx.doi.org/10.1016/0020-0255(90)90030-e}, DOI={10.1016/0020-0255(90)90030-e}, number={3}, journal={Information Sciences}, publisher={Elsevier BV}, author={Ming-Te, Chao and Franco, John}, year={1990}, month=aug, pages={289–314} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        7,
        14
      ]
    ],
    "date-time": "2025-07-14T02:34:33Z",
    "timestamp": 1752460473382
  },
  "reference-count": 11,
  "publisher": "Elsevier BV",
  "issue": "3",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1990,
            8,
            1
          ]
        ],
        "date-time": "1990-08-01T00:00:00Z",
        "timestamp": 649468800000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "https://www.elsevier.com/tdm/userlicense/1.0/"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1990,
        8
      ]
    ]
  },
  "DOI": "10.1016/0020-0255(90)90030-e",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2003,
        6,
        30
      ]
    ],
    "date-time": "2003-06-30T17:28:37Z",
    "timestamp": 1056994117000
  },
  "page": "289-314",
  "source": "Crossref",
  "is-referenced-by-count": 77,
  "title": "Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem",
  "prefix": "10.1016",
  "volume": "51",
  "author": [
    {
      "given": "Chao",
      "family": "Ming-Te",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "John",
      "family": "Franco",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "78",
  "reference": [
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB1",
      "doi-asserted-by": "crossref",
      "first-page": "583",
      "DOI": "10.1137/0210043",
      "article-title": "An average time analysis of backtracking",
      "volume": "10",
      "author": "Brown",
      "year": "1981",
      "journal-title": "SIAM J. Comput."
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB2",
      "article-title": "Probabilistic Analysis and Performance Measurement of Algorithms for the Satisfiability Problem",
      "author": "Chao",
      "year": "1984"
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB3",
      "doi-asserted-by": "crossref",
      "first-page": "1106",
      "DOI": "10.1137/0215080",
      "article-title": "Probabilistic analysis of two heuristics for the 3-satisfiability problem",
      "volume": "15",
      "author": "Chao",
      "year": "1986",
      "journal-title": "SIAM J. Comput."
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB4",
      "doi-asserted-by": "crossref",
      "first-page": "201",
      "DOI": "10.1145/321033.321034",
      "article-title": "A computing procedure for quantification theory",
      "volume": "7",
      "author": "Davis",
      "year": "1960",
      "journal-title": "J. Assoc. Comput. Mach."
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB5",
      "series-title": "Probabilistic Methods in Combinatorics",
      "author": "Erdos",
      "year": "1974"
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB6",
      "doi-asserted-by": "crossref",
      "first-page": "103",
      "DOI": "10.1016/0020-0190(86)90051-7",
      "article-title": "On the probabilistic performance of algorithms for the satisfiability problem",
      "volume": "23",
      "author": "Franco",
      "year": "1986",
      "journal-title": "Inform. Process. Lett."
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB7",
      "doi-asserted-by": "crossref",
      "first-page": "77",
      "DOI": "10.1016/0166-218X(83)90017-3",
      "article-title": "Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem",
      "volume": "5",
      "author": "Franco",
      "year": "1983",
      "journal-title": "Discrete Appl. Math."
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB8",
      "series-title": "Proceedings of the 4th Workshop on Automated Deduction",
      "first-page": "1",
      "article-title": "Average case complexity of the satisfiability problem",
      "author": "Goldberg",
      "year": "1979"
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB9",
      "doi-asserted-by": "crossref",
      "first-page": "72",
      "DOI": "10.1016/0020-0190(82)90110-7",
      "article-title": "Average time analysis of simplified Davis-Putnam procedures",
      "volume": "15",
      "author": "Goldberg",
      "year": "1982",
      "journal-title": "Inform. Process. Lett."
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB10",
      "doi-asserted-by": "crossref",
      "first-page": "117",
      "DOI": "10.1016/S0004-3702(83)80007-1",
      "article-title": "Search rearrangement backtracking and polynomial average time",
      "volume": "21",
      "author": "Purdom",
      "year": "1983",
      "journal-title": "Artificial Intelligence"
    },
    {
      "key": "10.1016/0020-0255(90)90030-E_BIB11",
      "doi-asserted-by": "crossref",
      "first-page": "943",
      "DOI": "10.1137/0214067",
      "article-title": "The pure literal rule and polynomial average time",
      "volume": "14",
      "author": "Purdom",
      "year": "1985",
      "journal-title": "SIAM J. Comput."
    }
  ],
  "container-title": "Information Sciences",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://api.elsevier.com/content/article/PII:002002559090030E?httpAccept=text/xml",
      "content-type": "text/xml",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://api.elsevier.com/content/article/PII:002002559090030E?httpAccept=text/plain",
      "content-type": "text/plain",
      "content-version": "vor",
      "intended-application": "text-mining"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        3,
        18
      ]
    ],
    "date-time": "2019-03-18T13:22:51Z",
    "timestamp": 1552915371000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://linkinghub.elsevier.com/retrieve/pii/002002559090030E"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1990,
        8
      ]
    ]
  },
  "references-count": 11,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          1990,
          8
        ]
      ]
    }
  },
  "alternative-id": [
    "002002559090030E"
  ],
  "URL": "http://dx.doi.org/10.1016/0020-0255(90)90030-E",
  "relation": {},
  "ISSN": [
    "0020-0255"
  ],
  "subject": [],
  "container-title-short": "Information Sciences",
  "published": {
    "date-parts": [
      [
        1990,
        8
      ]
    ]
  }
}