Concepedia

Boolean Satisfiability

Boolean Satisfiability is a decision problem in computational logic that determines whether there exists a truth assignment to a finite set of Boolean variables that satisfies a given propositional logic formula expressed in conjunctive normal form.

1.8K

Publications

109.5K

Citations

2.9K

Authors

919

Institutions

Publications per year

2017–2026

314

Parents

Publications

1.8K

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Michel X. Goemans, David P. Williamson · Journal of the ACM · 1995 · 3.7K citations · Full text

, , +14

Chaff

Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations

, , +12

The complexity of satisfiability problems

Thomas J. Schaefer · 1978 · 1.8K citations · Full text

, , +12

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani et al. · Journal of the ACM · 1998 · 1.4K citations · Full text

, , +14

GRASP: a search algorithm for propositional satisfiability

João Marques‐Silva, Karem A. Sakallah · IEEE Transactions on Computers · 1999 · 1.4K citations

, , +16

1–5 of 1.8K

Authors

2.9K

  1. JM
    João Marques‐Silva

    Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento, Portugal

    50 publications · 3.5K citations

    27

    h-index

  2. KA
    Karem A. Sakallah

    University of Michigan, United States

    33 publications · 3.3K citations

    25

    h-index

  3. RD
    Rolf Drechsler

    University of Bremen, Germany

    43 publications · 1.7K citations

    24

    h-index

  4. SM
    Sharad Malik

    Princeton University, United States

    25 publications · 5.4K citations

    23

    h-index

  5. RW
    Robert Wille

    Johannes Kepler University of Linz, Austria

    21 publications · 1K citations

    19

    h-index

1–5 of 2.9K

Institutions

919

  1. University of California, Berkeley

    Berkeley, United States

    37 h-index

    129 publications

    14.9K citations

  2. Centre National de la Recherche Scientifique

    Paris, France

    32 h-index

    111 publications

    10K citations

  3. Carnegie Mellon University

    Pittsburgh, United States

    30 h-index

    86 publications

    6.3K citations

  4. University of Toronto

    Toronto, Canada

    29 h-index

    98 publications

    7K citations

  5. Princeton University

    Princeton, United States

    27 h-index

    93 publications

    17.4K citations

  6. University of Michigan

    Ann Arbor, United States

    27 h-index

    94 publications

    6.8K citations

  7. University of Bremen

    Bremen, Germany

    24 h-index

    135 publications

    5.1K citations

  8. Stanford University

    Stanford, United States

    23 h-index

    73 publications

    8.5K citations

1–8 of 919

Venues

  1. 25

    h-index

  2. Journal of Artificial Intelligence Research

    JAIR · 32 publications · 2.8K citations

    23

    h-index

  3. arXiv (Cornell University)

    Repository · 50 publications · 1.6K citations

    22

    h-index

  4. 21

    h-index

  5. Theoretical Computer Science

    29 publications · 1.4K citations

    20

    h-index

1–5