Listing Maximal Independent Sets with Minimal Space and Bounded Delay

Abstract : An independent set is a set of nodes in a graph such that no two of them are adjacent. It is maximal if there is no node outside the independent set that may join it. Listing maximal independent sets in graphs can be applied, for example, to sample nodes belonging to different communities or clusters in network analysis and document clustering. The problem has a rich history as it is related to maximal cliques, dominance sets, vertex covers and 3-colorings in graphs. We are interested in reducing the delay, which is the worst-case time between any two consecutively output solutions, and the memory footprint, which is the additional working space behind the read-only input graph.
Type de document :
Communication dans un congrès
Gabriele Fici; Marinella Sciortino; Rossano Venturini. International Symposium on String Processing and Information Retrieval (SPIRE), Sep 2017, Palermo, Italy. Springer, String Processing and Information Retrieval, 10508 (1-2), pp.144-160, 2017, Lecture Notes in Computer Science. 〈10.1007/978-3-319-67428-5_13〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01609012
Contributeur : Marie-France Sagot <>
Soumis le : mardi 3 octobre 2017 - 11:47:36
Dernière modification le : mercredi 11 avril 2018 - 01:55:17

Fichier

conte_etal_2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno, Luca Versari. Listing Maximal Independent Sets with Minimal Space and Bounded Delay. Gabriele Fici; Marinella Sciortino; Rossano Venturini. International Symposium on String Processing and Information Retrieval (SPIRE), Sep 2017, Palermo, Italy. Springer, String Processing and Information Retrieval, 10508 (1-2), pp.144-160, 2017, Lecture Notes in Computer Science. 〈10.1007/978-3-319-67428-5_13〉. 〈hal-01609012〉

Partager

Métriques

Consultations de la notice

95

Téléchargements de fichiers

39