Abstract
For a hypergraph H(V,E), let = {Si,S2,...,Sr} be a family of subsets of V such that each St is a subset of some hyperedge of E. A -transversal problem is to find a minimum subfamily of such that a hyperedge of H contains a member of whenever it contains a member of. This problem reduces to the transversal problem when = V and each St is a singleton set consisting of a vertex of V. The.FQ-dique transversal problem becomes a particular case of transversal problem when hyperedges are the maximal cliques and is the family of all cliques of size I. We give an NC-algorithm to solve-transversal problem on totally balanced hypergraphs. The main result of this paper is that the.fQ-clique transversal on strongly chordal graphs is solvable in polylogarithmic. time with polynomial number of processors.
| Original language | English |
|---|---|
| Pages (from-to) | 3-14 |
| Number of pages | 12 |
| Journal | Australasian Journal of Combinatorics |
| Volume | 33 |
| State | Published - 2005 |
Fingerprint
Dive into the research topics of 'Parallel algorithms for generalized clique transversal problems'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver