Skip to main navigation Skip to search Skip to main content

Parallel algorithms for generalized clique transversal problems

  • Institut fur Informatik
  • University of Bonn
  • Graduate School of ITMS
  • Federation University Australia

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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 languageEnglish
Pages (from-to)3-14
Number of pages12
JournalAustralasian Journal of Combinatorics
Volume33
StatePublished - 2005

Fingerprint

Dive into the research topics of 'Parallel algorithms for generalized clique transversal problems'. Together they form a unique fingerprint.

Cite this