On the complexity of the k-chain subgraph cover problem
| Autor: | Gen-Huey Chen, Tze-Heng Ma, Chang-Wu Yu |
|---|---|
| Rok vydání: | 1998 |
| Předmět: |
Discrete mathematics
Bipartite graph Mathematics::Combinatorics General Computer Science Subgraph isomorphism problem Convex bipartite graph Complete bipartite graph Theoretical Computer Science Combinatorics Computer Science::Discrete Mathematics Comparability graph TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Cograph Induced subgraph isomorphism problem NC class P class Parallel random access machine Mathematics Forbidden graph characterization Distance-hereditary graph MathematicsofComputing_DISCRETEMATHEMATICS Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 205(1-2):85-98 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(97)00036-4 |
| Popis: | The k-chain subgraph cover problem asks if the edge set of a given bipartite graph G is the union of the edge sets of k chain graphs, where each chain graph is a subgraph of G. Although the k-chain subgraph cover problem is known to be NP-complete for the class of bipartite graphs, it is still unknown whether this problem is NP-complete or polynomial-time solvable for subclasses of bipartite graphs. In this paper, we answer this question partially by showing that this problem for an important subclass of bipartite graphs, termed convex bipartite graphs, belongs to not only the class P, but also the class NC. More specifically, we show that the k-chain subgraph cover problem on the convex bipartite graph can be solved in O(m2) time sequentially or O(log2n) time in parallel using O(m3) processors on the CRCW PRAM, where n and m denote the number of vertices and edges, respectively. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect