Show simple item record

dc.contributor.authorPottié, Olivier
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorMilis, Ioannis
dc.contributor.authorLucarelli, Giorgio
dc.contributor.authorGiannakos, Aristotelis
dc.contributor.authorBourgeois, Nicolas
dc.date.accessioned2010-11-09T16:34:38Z
dc.date.available2010-11-09T16:34:38Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5027
dc.language.isoenen
dc.subjectpolynomially equivalenten
dc.subjectgraphen
dc.subjectturing machineen
dc.subjectsecurity protocolsen
dc.subjectquantum computationen
dc.subjectmaximum spanning treeen
dc.subjectcomputabilityen
dc.subject.ddc511en
dc.titleThe Max Quasi-Independent Set Problemen
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherDepartment of Informatics, Athens University of Economics and Business;Grèce
dc.description.abstractenIn this paper, we deal with the problem of finding quasi- independent sets in graphs. This problem is formally defined 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 , finding 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 specifically defined γ-QIS and k-QIS problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.en
dc.identifier.citationpages60-72en
dc.relation.ispartoftitleComputer Science – Theory and Applications 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedingsen
dc.relation.ispartofeditorMayr, Ernst W.
dc.relation.ispartofeditorAblayev, Farid
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2010
dc.relation.ispartofpages397en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-13182-0en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-642-13181-3en
dc.relation.conftitle5th International Computer Science Symposium in Russia, CSR 2010en
dc.relation.confdate2010-06
dc.relation.confcityKazanen
dc.relation.confcountryRussieen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record