Transversal partitioning in balanced hypergraphs
type: Item
instance of: scholarly article
title: Transversal partitioning in balanced hypergraphs
zbMATH Open document ID: 0887.05039
DOI: 10.1016/S0166-218X(97)00034-6
author: Elias Dahlhaus
author: Paul Manuel
author: Mirka Miller
author: Jan Kratochvíl
published in: Discrete Applied Mathematics
publication date: 1997-11-18T00:00:00Z
full work available at URL: dam
review text: The problem of partitioning transversals of a hypergraph into pairwise disjoint transversals is studied. A \(k\)-fold transversal of a hypergraph is a set of vertices that contains at least \(k\) elements of every hyperedge. The main result is that in a balanced hypergraph for every \(k\leq\gamma\), where \(\gamma\) is the minimum cardinality of a hyperedge, each \(k\)-fold transversal can be partitioned in polynomial time into \(k\) pairwise disjoint 1-fold transversals. For totally balanced hypergraphs also an NC algorithm is given. As a corollary it is deduced e.g. that the dominating partition problem, i.e. to find a partition of the vertex set of a graph into a maximal number of dominating sets, is in NC for strongly chordal graphs, whereas for general chordal graphs this problem is known to be NP-complete.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1088855
zbMATH Keywords: transversals
zbMATH Keywords: hypergraph
zbMATH Keywords: NC algorithm
zbMATH Keywords: dominating partition problem
zbMATH Keywords: dominating sets
zbMATH Keywords: strongly chordal graphs
reviewed by: Martin Middendorf
MaRDI profile type: Publication
cites work: Q4065051
cites work: Balanced matrices
cites work: Q3941433
cites work: Dominating sets and domatic number of circular arc graphs
cites work: Graphs whose neighborhoods have no special cycles
cites work: Deterministic coin tossing with applications to optimal parallel list ranking
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q4198056
cites work: Q4023519
cites work: The domatic number problem on some perfect graph families
cites work: Parallel Prefix Computation
cites work: Doubly Lexical Orderings of Matrices
cites work: A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
cites work: Q4288086
cites work: Linear algorithm for domatic number problem on interval graphs
cites work: An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model
OpenAlex ID: W1973391616
description: scientific article; zbMATH DE number 1088855