perm filename TEN.PUB[BIB,CSR]1 blob sn#539101 filedate 1980-10-02 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00003 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .require "setup.csr[bib,csr]" source file C00004 00003 %3STAN-CS-80-822: C00007 ENDMK C⊗; .require "setup.csr[bib,csr]" source file; .once center %3Stanford University Computer Science Reports%1 List Number 10↔December 1980 Listed here are abstracts of the most recent reports published by the Department of Computer Science at Stanford University. %3Request Reports:%1 Complete the enclosed order form, and return the entire order form page (including mailing label) as soon as possible. In many cases we can print only a limited number of copies, and requests will be filled on a first come, first served basis as the reports become available. If the code (FREE) is printed on your mailing label, you will not be charged for hardcopy. This exemption from payment is limited primarily to libraries. (The costs shown include all applicable sales taxes. %2Please send no money now, wait until you get an invoice%1.) %3Alternatively:%1 Copies of most Stanford CS Reports may be obtained by writing (about 2 months after the "Most Recent CS Reports" listing) to National Technical Information Service, 5285 Port Royal Road, Springfield, Virginia 22161. Stanford Ph.D. theses are available from University Microfilms, 300 North Zeeb Road, Ann Arbor, Michigan 48106. -↔- %3STAN-CS-80-822: %2Efficient Algorithms for certain Satisfiability and Linear Programming Problems%1 by Bengt Aspvall (Thesis, ? pages, September 1980) We present efficient algorithms for certain cases of Linear Equations solving, Linear Programming, and SATisfiability testing. LE, LP, and SAT have all been studied in both the theoretical and the applied areas of Computer Science. Although many algorithms have been developed for these problems, there are large gaps between today's best algorithms and the best theoretical lower bounds. We do not eliminate these gaps, but instead present efficient algorithms for LE, LP, and SAT (and for testing the truth of Quantified Boolean Formulas) for the cases in which there are at most two variables or literals per equation, inequality, or clause. These subcases seem to be the "hardest" ones that are not as hard as the general problems. The algorithms for LE(2), 2-SAT, and 2-QBF are linear-time algorithms, and they are optimal except for constant factors. Our algorithm for the subcase of LP has a nonlinear worst-case bound, but the bound is better than for any general LP algorithm such as the polynomial-time algorithm by Khachiyan, and the algorithm seems to be of practical as well as theoretical importance. In the algorithms, we associate graphs with given problem instances. By performing searches on the graphs (in the LP case combined with a binary search technique), we construct a solution or a satisfying truth assignment if one exists. We present also a linear-time algorithm, which uses the 2-SAT algorithm, for mapping certain Boolean expressions in Conjunction Normal Form to equivalent CNF expressions having at most one negated variable per clause (without increasing the length of the expression); such CNF expressions can be tested for satisfiability in linear time. -↔-