On the average-case complexity of parameterized clique

The k -Clique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of res...

Full description

Bibliographic Details
Published in:Theoretical computer science : the journal of the EATCS, Vol. 576 (2015), p. 18-29
Main Author: Fountoulakis, Nikolaos
Other Involved Persons: Friedrich, Tobias ; Hermelin, Danny
Format: electronic Article
Language:English
Physical Description:Online-Ressource
DOI:10.1016/j.tcs.2015.01.042
QR Code: Show QR Code