Search
for Author
All Reviews
Beigel, Richard
Options:
All Media Types
Journals
Proceedings
Div Books
Whole Books
Other
Date Reviewed
Title
Author
Publisher
Published Date
Descending
Ascending
Date Reviewed
1
-
2
of
2
reviews
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.3289
n
). The previous record for this problem was the
O
(1....
...
Jul 5 2005
PP is closed under intersection
Beigel R., Reingold N., Spielman D. Theory of computing (Proceedings of the twenty-third annual ACM symposium, New Orleans, Louisiana, United States, May 5-8, 1991) 1-9, 1991. Type: Proceedings
PP (probabilistic polynomial time) was first studied in the 1970s, and basic properties of the class have been known since then (for instance, NP ⊆ PP, and PP is closed under complement). It had remained an open question wheth...
...
Oct 1 1991
Reproduction in whole or in part without permission is prohibited. Copyright 1999-2024 ThinkLoud
®
Terms of Use
|
Privacy Policy