Nearly-perfect hypergraph packing is in NC

DOI10.1016/S0020-0190(96)00181-0zbMATH Open1336.68127MaRDI QIDQ286955FDOQ286955

Authors: David A. Grable 

Publication date: 26 May 2016

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

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

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)

Cites Work

• Reducibility among combinatorial problems
• On a packing and covering problem
• Near perfect coverings in graphs and hypergraphs
• Asymptotic behavior of the chromatic index for hypergraphs
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

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

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)