𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of the k-chain subgraph cover problem

✍ Scribed by Yu Chang-Wu; Chen Gen-Huey; Ma Tze-Heng

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
776 KB
Volume
205
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 X--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 0(m2) time sequentially or O(log*n) time in parallel using 0(m3) processors on the CRCW PRAM, where n and m denote the number of vertices and edges, respectively.

πŸ“œ SIMILAR VOLUMES

On the complexity of the pancake problem
On the complexity of the pancake problem
✍ Fuxiang Yu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, called __the pancake problem__, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main resul

On the complexity of the car sequencing
On the complexity of the car sequencing problem
✍ TamΓ‘s Kis πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 190 KB

In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of NP-completeness is incorrect, and instead we give a su cient condition of membership of NP. We also provide a ps

On the Complexity of k-SAT
On the Complexity of k-SAT
✍ Russell Impagliazzo; Ramamohan Paturi πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 114 KB

The k-SAT problem is to determine if a given k-CNF has a satisfying assignment. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k 3. Here exponential time means 2 $n for some $>0. In this paper, assuming that, for k 3, k-SAT requires exponential time co