In this paper, we address three related problems. One is the enumeration of all the maximal edge-induced chain subgraphs of a bipartite graph. We give bounds on their number and use them to establish the input-sensitive complexity of the enumeration problem. The second problem we treat is the minimum chain subgraph cover. Finally, we approach the problem of enumerating all minimal chain subgraph covers 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 Proceedings of the 17th Italian Conference on Theoretical Computer Science, Lecce, Italy, September 7-9, 2016. CEUR Workshop Proceedings (pp. 286- 291). https://ceur-ws.org/Vol-1720/.
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. We give bounds on their number and use them to establish the input-sensitive complexity of the enumeration problem. The second problem we treat is the minimum chain subgraph cover. Finally, we approach the problem of enumerating all minimal chain subgraph covers and show that it can be solved in quasi-polynomial time.
| File | Dimensione | Formato | |
|---|---|---|---|
|
short12.pdf
Open Access
Tipologia:
Versione dell'editore
Licenza:
Copyright dell'editore (accesso aperto)
Dimensione
315.54 kB
Formato
Adobe PDF
|
315.54 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
