On Maximal Chain Subgraphs and Covers of Bipartite Graphs - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

On Maximal Chain Subgraphs and Covers of Bipartite Graphs

(1) , (1, 2, 3) , (2, 4) , (2, 4) , (2, 4)


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.
Fichier principal
Vignette du fichier
PaperIWOCA2016.pdf (123.37 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01388546 , version 1 (30-05-2017)



Tiziana Calamoneri, Mattia Gastaldello, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri. On Maximal Chain Subgraphs and Covers of Bipartite Graphs. Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Aug 2016, Helsinki, Finland. pp.137-150, ⟨10.1007/978-3-319-44543-4_11⟩. ⟨hal-01388546⟩
136 View
185 Download



Gmail Facebook Twitter LinkedIn More