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.
Calamoneri, T.; Gastaldello, M.; Mary, A.; Sagot, M. -F.; Sinaimeri, Blerina. (2016). On maximal chain subgraphs and covers of bipartite graphs. In International Workshop on Combinatorial Algorithms, IWOCA (pp. 137- 150). Isbn: 978-3-319-44542-7. Isbn: 978-3-319-44543-4. Doi: 10.1007/978-3-319-44543-4_11.
On maximal chain subgraphs and covers of bipartite graphs
Sinaimeri B.
2016
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.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
