Transversal partitioning in balanced hypergraphs

DOI10.1016/S0166-218X(97)00034-6zbMath0887.05039OpenAlexW1973391616MaRDI QIDQ1372732

Elias Dahlhaus, Mirka Miller, Paul D. Manuel, Jan Kratochvíl

Publication date: 18 November 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

hypergraphtransversalsdominating setsstrongly chordal graphsNC algorithmdominating partition problem

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (2)

Variations of maximum-clique transversal sets on graphs ⋮ The geodesic-transversal problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Graphs whose neighborhoods have no special cycles
• Dominating sets and domatic number of circular arc graphs
• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model
• Linear algorithm for domatic number problem on interval graphs
• The domatic number problem on some perfect graph families
• Deterministic coin tossing with applications to optimal parallel list ranking
• Doubly Lexical Orderings of Matrices
• Parallel Prefix Computation
• Balanced matrices

This page was built for publication: Transversal partitioning in balanced hypergraphs