On Maximal Chain Subgraphs and Covers of Bipartite Graphs

Abstract : In this paper, we address three related problems. One is the enumeration of all the maximal edge induced chain subgraphs of a bipartite graph, for which we provide a polynomial delay algorithm. We give bounds on the number of maximal chain subgraphs for a bipartite graph and use them to establish the input-sensitive complexity of the enumeration problem. The second problem we treat is the one of finding the minimum number of chain subgraphs needed to cover all the edges a bipartite graph. For this we provide an exact exponential algorithm with a non trivial complexity. Finally, we approach the problem of enumerating all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time.
Type de document :
Communication dans un congrès
Veli Mäkinen; Simon J. Puglisi; Leena Salmela. Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Aug 2016, Helsinki, Finland. Springer, Lecture Notes in Computer Science, 9843, pp.137-150, 2016, Combinatorial Algorithms. 〈10.1007/978-3-319-44543-4_11〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01388546
Contributeur : Marie-France Sagot <>
Soumis le : mardi 30 mai 2017 - 14:06:54
Dernière modification le : jeudi 28 juin 2018 - 14:38:27
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 13:54:56

Fichier

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

Identifiants

Collections

Citation

Tiziana Calamoneri, Mattia Gastaldello, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri. On Maximal Chain Subgraphs and Covers of Bipartite Graphs. Veli Mäkinen; Simon J. Puglisi; Leena Salmela. Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Aug 2016, Helsinki, Finland. Springer, Lecture Notes in Computer Science, 9843, pp.137-150, 2016, Combinatorial Algorithms. 〈10.1007/978-3-319-44543-4_11〉. 〈hal-01388546〉

Partager

Métriques

Consultations de la notice

231

Téléchargements de fichiers

51