Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem): Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
Tag: Reverted
No edit summary
Tag: Manual revert
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Time Complexity ==  
== Time Complexity ==  


$O(kn + {1.2852}^k)$
$O({1.2738}^k+ kn)$


== Space Complexity ==  
== Space Complexity ==  


$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words
$O(poly(n))$ words


(First auxiliary graph contains O(k^2) edges; algorithm subsequently branches to a depth of O(k) (each fork being degree O(1)), with a new O(k^2)-sized graph at each depth. Interleaving shouldn't increase space usage asymptotically. (Could possibly be reduced to O(k) by just keeping track of graph deltas?) (but also a different source claims exponential?))
(https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf)


== Description ==  
== Description ==  
Line 27: Line 27:
== Year ==  
== Year ==  


2001
2006


== Reference ==  
== Reference ==  


https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.4800&rep=rep1&type=pdf
https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf

Latest revision as of 10:33, 28 April 2023

Time Complexity

$O({1.2738}^k+ kn)$

Space Complexity

$O(poly(n))$ words

(https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2006

Reference

https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Chen;_I._Kanj;_and_W._Jia._(The_Vertex_Cover_Problem_The_Vertex_Cover_Problem)&oldid=47822"