| dc.contributor.author | Pottié, Olivier | |
| dc.contributor.author | Paschos, Vangelis | |
| dc.contributor.author | Milis, Ioannis | |
| dc.contributor.author | Lucarelli, Giorgio | |
| dc.contributor.author | Giannakos, Aristotelis | |
| dc.contributor.author | Bourgeois, Nicolas | |
| dc.date.accessioned | 2010-11-09T16:34:38Z | |
| dc.date.available | 2010-11-09T16:34:38Z | |
| dc.date.issued | 2010 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/5027 | |
| dc.language.iso | en | en |
| dc.subject | polynomially equivalent | en |
| dc.subject | graph | en |
| dc.subject | turing machine | en |
| dc.subject | security protocols | en |
| dc.subject | quantum computation | en |
| dc.subject | maximum spanning tree | en |
| dc.subject | computability | en |
| dc.subject.ddc | 511 | en |
| dc.title | The Max Quasi-Independent Set Problem | en |
| dc.type | Communication / Conférence | |
| dc.contributor.editoruniversityother | Department of Informatics, Athens University of Economics and Business;Grèce | |
| dc.description.abstracten | 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. | en |
| dc.identifier.citationpages | 60-72 | en |
| dc.relation.ispartoftitle | Computer Science – Theory and Applications 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings | en |
| dc.relation.ispartofeditor | Mayr, Ernst W. | |
| dc.relation.ispartofeditor | Ablayev, Farid | |
| dc.relation.ispartofpublname | Springer | en |
| dc.relation.ispartofpublcity | Berlin | en |
| dc.relation.ispartofdate | 2010 | |
| dc.relation.ispartofpages | 397 | en |
| dc.relation.ispartofurl | http://dx.doi.org/10.1007/978-3-642-13182-0 | en |
| dc.description.sponsorshipprivate | oui | en |
| dc.subject.ddclabel | Principes généraux des mathématiques | en |
| dc.relation.ispartofisbn | 978-3-642-13181-3 | en |
| dc.relation.conftitle | 5th International Computer Science Symposium in Russia, CSR 2010 | en |
| dc.relation.confdate | 2010-06 | |
| dc.relation.confcity | Kazan | en |
| dc.relation.confcountry | Russie | en |
