COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "setup.csr[bib,csr]" source file
C00004 00003	%3STAN-CS-80-822:
C00007 00004	%3STAN-CS-80-823:
C00010 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.

-↔-

%3STAN-CS-80-823:
%2Knowledge-Based Retrieval on a Relational Database Machine%1
by David Elliot Shaw (Thesis, 280 pages, August 1980)

-↔-