• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

The Max Quasi-Independent Set Problem

Thumbnail
View/Open
qiscah-1.pdf (548.6Kb)
Date
2010
Dewey
Principes généraux des mathématiques
Sujet
polynomially equivalent; graph; turing machine; security protocols; quantum computation; maximum spanning tree; computability
Conference name
5th International Computer Science Symposium in Russia, CSR 2010
Conference date
06-2010
Conference city
Kazan
Conference country
Russie
Book title
Computer Science – Theory and Applications 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings
Author
Mayr, Ernst W.; Ablayev, Farid
Publisher
Springer
Publisher city
Berlin
Year
2010
Pages number
397
ISBN
978-3-642-13181-3
Book URL
http://dx.doi.org/10.1007/978-3-642-13182-0
URI
https://basepub.dauphine.fr/handle/123456789/5027
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Pottié, Olivier
Paschos, Vangelis
Milis, Ioannis
Lucarelli, Giorgio
Giannakos, Aristotelis
Bourgeois, Nicolas
Type
Communication / Conférence
Item number of pages
60-72
Abstract (EN)
In 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.