| |
1-10 of 27 reviews |
Date Reviewed | |
| |
Model checking with Boolean satisfiability
Marques-Silva J. Journal of Algorithms 63(1-3): 3-16, 2008. Type: Article
Model checking of finite state transition systems has interesting applications in hardware verification. Boolean satisfiability (SAT) algorithms have proven to be very effective for this purpose. This paper captures the trends of the S...
|
Dec 19 2008 |
|
| |
 Insufficiency of four known necessary conditions on string unavoidability
Heitsch C. Journal of Algorithms 56(2): 96-123, 2005. Type: Article
Pattern matching is difficult. If you’ve ever doubted this, consider string unavoidability, the topic of this paper....
|
May 8 2006 |
|
| |
On fairness in the carpool problem
Naor M. Journal of Algorithms 55(1): 93-98, 2005. Type: Article
Carpooling is a common practice among people who each have a car, but travel together to save costs. The problem of implementing a fair carpooling system consists of defining what a fair share is, and designing an algorithm to decide w...
|
Oct 20 2005 |
|
| |
Efficient parallel exponentiation in GF(q) using normal basis representations
Lee M., Kim Y., Park K., Cho Y. Journal of Algorithms 54(2): 205-221, 2005. Type: Article
Finite field arithmetic has important applications in cryptography and coding theory. In recent years, various efficient algorithms have been developed using the normal basis representation, where every element in GF...
|
Jul 26 2005 |
|
| |
3-coloring in time O(1.3289)
Beigel R., Eppstein D. Journal of Algorithms 54(2): 168-204, 2005. Type: Article
The main result of this paper is a proof that the three-coloring problem can be solved in worst-case time O(1.3289n). The previous record for this problem was the O(1....
|
Jul 5 2005 |
|
| |
An algorithm for the satisfiability problem of formulas in conjunctive normal form
Schuler R. Journal of Algorithms 54(1): 40-44, 2005. Type: Article
Nondeterministic polynomial time (NP) complete problems have always been an attractive field of research to an army of scientists. Because of their complexity, even algorithms that would contribute to a miniscule decrease in complexity...
|
May 3 2005 |
|
| |
Factoring into coprimes in essentially linear time
Bernstein D. Journal of Algorithms 54(1): 1-30, 2005. Type: Article
This paper concerns factorization in commutative multiplicative monoids, with particular emphasis on the multiplicative monoids of integers and polynomials over a finite field. In particular, if M is such a monoid, a...
|
Apr 27 2005 |
|
| |
On external-memory MST, SSSP and multi-way planar graph separation
Arge L., Brodal G., Toma L. Journal of Algorithms 53(2): 186-206, 2004. Type: Article
Given the multi-gigabyte main memories of today’s computers, one might wonder why the efficient use of external memory is still an issue. It’s important to realize that the sizes of the problems computers are being ...
|
Mar 23 2005 |
|
| |
Distance labeling in graphs
Gavoille C., Peleg D., Pérennes S., Raz R. Journal of Algorithms 53(1): 85-112, 2004. Type: Article
This paper mainly addresses the problem of efficiently labeling graphs in such a way that the distance between two nodes of the graph can be computed only from their labels. Of course, it is desirable to have the maximum length of a la...
|
Jan 26 2005 |
|
| |
All-norm approximation algorithms
Azar Y., Epstein L., Richter Y., Woeginger G. Journal of Algorithms 52(2): 120-133, 2004. Type: Article
In optimization problems, especially in scheduling problems for different measures, there might be different optimal solutions. In this work, the authors introduce the concept of an all-norm ρ-approximation algorithm for the pr...
|
Nov 11 2004 |
|
| |
|
|
| |
|
|
|
|
