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.
On maximal chain subgraphs and covers of bipartite graphs / Calamoneri, Tiziana; Gastaldello, Mattia; Mary, Arnaud; Sagot Marie, France; Sinaimeri, Blerina. - ELETTRONICO. - 9843:(2016), pp. 137-150. (Intervento presentato al convegno IWOCA 2016 tenutosi a Helsinki nel 17-19 August 2016) [10.1007/978-3-319-44543-4].
On maximal chain subgraphs and covers of bipartite graphs
CALAMONERI, Tiziana;
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.File | Dimensione | Formato | |
---|---|---|---|
Calamoneri_Maximal_2016.pdf
accesso aperto
Note: Articolo presentato alla conferenza
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
119.49 kB
Formato
Adobe PDF
|
119.49 kB | Adobe PDF | |
Calamoneri_Maximal_2016.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
245.73 kB
Formato
Adobe PDF
|
245.73 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.