Nearly-perfect hypergraph packing is in NC

DOI10.1016/S0020-0190(96)00181-0MaRDI QIDQ286955zbMATH OpenFDO

Authors 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) Randomized algorithms (68W20) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Recommendations

• ECONOMICAL COVERS WITH GEOMETRIC APPLICATIONS
• More-than-nearly-perfect packings and partial designs
• Publication:4885222
• Constructing a perfect matching is in random NC
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density

Cites work

• scientific article; zbMATH DE number 3970750 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 903456 (Why is no real title available?)
• scientific article; zbMATH DE number 3198027 (Why is no real title available?)
• 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
• Asymptotic behavior of the chromatic index for hypergraphs
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Constructing a perfect matching is in random NC
• Matchings and covers in hypergraphs
• More-than-nearly-perfect packings and partial designs
• Near perfect coverings in graphs and hypergraphs
• On a packing and covering problem
• Reducibility among combinatorial problems

Cited in

(10)

• Constructive Packings of Triple Systems
• Constructive packings by linear hypergraphs
• New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
• Integer and fractional packings of hypergraphs
• On a hypergraph matching problem
• Concentration of non‐Lipschitz functions and applications
• 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
• Packing directed cycles efficiently

This page was built for publication: Nearly-perfect hypergraph packing is in NC

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