Transversal partitioning in balanced hypergraphs

DOI10.1016/S0166-218X(97)00034-6MaRDI QIDQ1372732zbMATH OpenOpenAlexFDO

Authors Elias Dahlhaus, Paul Manuel, Mirka Miller, 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

dominating setshypergraphtransversalsstrongly chordal graphsNC algorithmdominating partition problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2230915
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• scientific article; zbMATH DE number 5440
• Independent transversals of hypergraph edges and bipartite bigraphs

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• 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
• Balanced matrices
• Deterministic coin tossing with applications to optimal parallel list ranking
• Dominating sets and domatic number of circular arc graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Doubly Lexical Orderings of Matrices
• Graphs whose neighborhoods have no special cycles
• Linear algorithm for domatic number problem on interval graphs
• Parallel Prefix Computation
• The domatic number problem on some perfect graph families

Cited in

(5)

• Maximum \(h\)-colourable subgraph problem in balanced graphs
• The geodesic-transversal problem
• Variations of maximum-clique transversal sets on graphs
• Partitioning of loop-free sperner hypergraphs into transversals
• scientific article; zbMATH DE number 2230915 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1372732)