On maximal chain subgraphs and covers of bipartite graphs
| Autor: | Blerina Sinaimeri, Arnaud Mary, Tiziana Calamoneri, Marie-France Sagot, Mattia Gastaldello |
|---|---|
| Přispěvatelé: | Dipartimento di Informatica, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Baobab, Département PEGASE [LBBE] (PEGASE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Veli Mäkinen, Simon J. Puglisi, Leena Salmela, ANR-15-CE40-0009,GraphEn,Enumération dans les graphes et les hypergraphes: algorithmes et complexité(2015), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] |
| Předmět: |
Matching (graph theory)
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0102 computer and information sciences 02 engineering and technology Enumeration Algorithms 01 natural sciences Complete bipartite graph law.invention Combinatorics Computer Science::Discrete Mathematics law TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Chain Subgraph Cover Problem Line graph 0202 electrical engineering electronic engineering information engineering Cograph Forbidden graph characterization Mathematics Discrete mathematics Mathematics::Combinatorics Foster graph Exact exponential algorithms [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM] Edge-transitive graph 010201 computation theory & mathematics Bipartite graph 020201 artificial intelligence & image processing MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Scopus-Elsevier Lecture Notes in Computer Science ISBN: 9783319445427 IWOCA Lecture Notes in Computer Science Combinatorial Algorithms-27th International Workshop, IWOCA 2016 Combinatorial Algorithms-27th International Workshop, IWOCA 2016, Aug 2016, Helsinki, Finland. pp.137-150, ⟨10.1007/978-3-319-44543-4_11⟩ |
| DOI: | 10.1007/978-3-319-44543-4_11⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|