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 metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01388546
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, May 30, 2017 - 2:06:54 PM
Last modification on : Thursday, November 21, 2019 - 1:14:17 PM
Long-term archiving on : Wednesday, September 6, 2017 - 1:54:56 PM

File

PaperIWOCA2016.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

287

Files downloads

579