Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, May 30, 2017 - 2:06:54 PM
Last modification on : Tuesday, July 20, 2021 - 5:20:05 PM
Long-term archiving on: : Wednesday, September 6, 2017 - 1:54:56 PM


Files produced by the author(s)




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⟩



Record views


Files downloads