Nearly-perfect hypergraph packing is in NC

DOI10.1016/S0020-0190(96)00181-0zbMath1336.68127MaRDI QIDQ286955

David A. Grable

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithmscomputational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20)

Related Items

Concentration of non‐Lipschitz functions and applications, Integer and fractional packings of hypergraphs, Packing directed cycles efficiently, Constructive Packings of Triple Systems, Graph and hypergraph colouring via nibble methods: a survey, New bounds on the size of nearly perfect matchings in almost regular hypergraphs, Combinatorial and computational aspects of graph packing and graph decomposition, Constructive Packings by Linear Hypergraphs, New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help, On a hypergraph matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of the chromatic index for hypergraphs
• On a packing and covering problem
• Near perfect coverings in graphs and hypergraphs
• Constructing a perfect matching is in random NC
• More-than-nearly-perfect packings and partial designs
• Matchings and covers in hypergraphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Reducibility among Combinatorial Problems