The Max Quasi-Independent Set Problem
Pottié, Olivier; Paschos, Vangelis; Milis, Ioannis; Lucarelli, Giorgio; Giannakos, Aristotelis; Bourgeois, Nicolas (2010), The Max Quasi-Independent Set Problem, in Mayr, Ernst W.; Ablayev, Farid, Computer Science – Theory and Applications 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings, Springer : Berlin, p. 60-72
TypeCommunication / Conférence
Conference title5th International Computer Science Symposium in Russia, CSR 2010
Book titleComputer Science – Theory and Applications 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings
Book authorMayr, Ernst W.; Ablayev, Farid
Number of pages397
MetadataShow full item record
Abstract (EN)In this paper, we deal with the problem of ﬁnding quasi- independent sets in graphs. This problem is formally deﬁned in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f-QIS, consists of, given a graph and a non- decreasing function f , ﬁnding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f (|Q|). For this problem, we show an exact solu- d−27/23 ∗ n tion method that runs within time O (2 d+1 ) on graphs of average degree bounded by d. For the most speciﬁcally deﬁned γ-QIS and k-QIS problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.
Subjects / Keywordspolynomially equivalent; graph; turing machine; security protocols; quantum computation; maximum spanning tree; computability
Showing items related by title and author.
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis; Pottié, Olivier (2012) Article accepté pour publication ou publié
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2017) Article accepté pour publication ou publié