| |
|
|
| |
| |
|
Date Reviewed |
|
| |
1 - 10 of 39
reviews
|
|
|
 |
|
|
|
|
Sturmian words, Lyndon words and trees
Berstel J., de Luca A. Theoretical Computer Science 178(1-2): 171-203, 1997. Type: Article
The authors present results on the structure, combinatorics, and arithmetic of PER, the set of all words w that have two periods p and q that are coprime and that satisfy
|
Feb 1 1998 |
|
|
|
|
|
|
On winning strategies in Ehrenfeucht-Fraïssé games
Arora S., Fagin R. Theoretical Computer Science 174(1-2): 97-121, 1997. Type: Article
Everyone is familiar with the computational complexity of a problem, namely, the amount of resources, such as time or space, required by a machine that solves the problem. Fewer are familiar with the descriptive complexity of a problem...
|
Dec 1 1997 |
|
|
|
|
|
|
Computational geometry
de Berg M., van Kreveld M., Overmars M., Schwarzkopf O., Springer-Verlag New York, Inc., Secaucus, NJ, 1997. Type: Book (9783540612704)
Computational geometry emerged from the field of algorithm design in the late 1970s. This textbook, written for a graduate course in computational geometry, makes a number of new algorithmic techniques accessible to students who know a...
|
Nov 1 1997 |
|
|
|
|
|
|
Tree structure for distributive lattices and its applications
Habib M., Nourine L. Theoretical Computer Science 165(2): 391-405, 1996. Type: Article
An ideal tree is a good data structure for a distributive lattice L = ( X , E ). It uses O ( | X | ) space and allows reachability, meet, and join operations to be computed in...
|
Oct 1 1997 |
|
|
|
|
|
|
On-line routing of virtual circuits with applications to load balancing and machine scheduling
Aspnes J., Azar Y., Fiat A., Plotkin S., Waarts O. Journal of the ACM 44(3): 486-504, 1997. Type: Article
Point-to-point circuit routing is a generalization of online load balancing. Jobs arrive online and must be assigned immediately. Assigning a job to a machine increases the machine’s load according to a load vector. All coord...
|
Oct 1 1997 |
|
|
|
|
|
|
Worst-case analysis of fast heuristics for packing squares into a square
Picouleau C. Theoretical Computer Science 164(1-2): 59-72, 1996. Type: Article
Consider the NP-complete problem of orthogonally packing a set of squares into a square of minimal size. The paper investigates three heuristics: next fit, next-fit decreasing, and first-fit decreasing. The paper proves that the first ...
|
Jul 1 1997 |
|
|
|
|
|
|
“Deco” polyominoes, permutations and random generation
Barcucci E., Del Lungo A., Pinzani R. (ed) Theoretical Computer Science 159(1): 29-42, 1996. Type: Article
A polyomino is an edge-connected, finite set of unit squares in the plane. It is column-convex if and only if its intersection with every column is edge-connected. A column-convex polyomino starts from a source cell and grows by adding...
|
May 1 1997 |
|
|
|
|
|
|
Computing solutions uniquely collapses the polynomial hierarchy
Hemaspaandra L. (ed), Naik A., Ogihara M., Selman A. (ed) SIAM Journal on Computing 25(4): 697-708, 1996. Type: Article
The authors examine the consequences of the existence of a nondeterministic function f that, when given a satisfiable formula F as input, outputs a satisfying assignment. That is, f is a nondeterministic function t...
|
Apr 1 1997 |
|
|
|
|
|
|
On the computational complexity of dynamic graph problems
Ramalingam G., Reps T. Theoretical Computer Science 158(1-2): 233-277, 1996. Type: Article
Suppose you are given a graph, G = ( V, E ), a graph problem, P, and an algorithm, A, to solve P. After you solve P using A
|
Feb 1 1997 |
|
|
|
|
|
|
Foundations of algorithms
Neapolitan R., Naimipour K., D. C. Heath and Company, Lexington, MA, 1996. Type: Book (9780669352986)
The authors discuss designing algorithms, complexity analysis of algorithms, and computational complexity, but do not cover analysis of correctness. The book is designed for computer science students who have had little calculus and ar...
|
Dec 1 1996 |
|
|
|
|
|
| |
|
|
| |
|
|
