- Title
- Parallel algorithms for generalized clique transversal problems
- Creator
- Miller, Mirka; Dahlhaus, Elias; Manuel, Paul
- Date
- 2005
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/35513
- Identifier
- vital:599
- Identifier
- ISSN:1034-4942
- Abstract
- The K ` - clique transversal problem is to locate a minimum collection of cliques of size ` in a graph G such that every maximal clique of size ` in G contains at least one member of the collection. We give an NC algorithm to solve this problem on strongly chordal graphs. Keywords: balanced graphs, strongly chordal graphs, clique transversal, k-fold clique transversal, K ` - clique transversal. 1 Introduction A 0 Gamma 1 matrix is balanced if it does not contain as a submatrix, an edge - vertex incidence matrix of an odd cycle. A 0 Gamma 1 matrix is totally balanced if it does not contain as a submatrix, an edge - vertex incidence matrix of any cycle. A hypergraph H is an ordered pair (V; E) where V is a set of vertices and E is a family of subsets of V . The members of E are called hyperedges of H . Let V = fv 1 ; v 2 ; : : : ; v n g and E = fE 1 ; E 2 ; : : : ; Em g. Let A(H) denote the hyperedge - vertex incidence matrix of a hypergraph H .; C1
- Publisher
- Queensland Centre for Discrete Mathematics & Computing
- Relation
- Australasian Journal of Combinatorics Vol. 33, no. (2005), p. 3-14
- Rights
- Open Access
- Rights
- Copyright Centre for Discrete Mathematics & Computing
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0101 Pure Mathematics; Balanced graphs; Strongly chordal graphs; Clique transversal; K-fold clique transversal; K - clique transversal
- Reviewed
- Hits: 3871
- Visitors: 3784
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|