The complexity of perfect packings in dense graphs

DOI10.1007/978-3-319-55911-7_21MaRDI QIDQ2988829zbMATH OpenOpenAlexFDO

Authors Jie Han

Publication date 19 May 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-55911-7_21

zbMATH Keywords

computational complexityabsorbing methodperfect packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The complexity of perfect matchings and packings in dense hypergraphs
• Packings in Dense Regular Graphs
• On perfect packings in dense graphs
• The minimum degree threshold for perfect graph packings
• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree

Cites work

• K₄⁻‐factor in a graph
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A geometric theory for hypergraph matching
• Combinatorial and computational aspects of graph packing and graph decomposition
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• Critical chromatic number and the complexity of perfect packings in graphs
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• Maximum bounded \(H\)-matching is Max SNP-complete
• On extremal problems of graphs and generalized graphs
• On the Complexity of General Graph Factor Problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Paths, Trees, and Flowers
• Perfect packings with complete graphs minus an edge
• Polynomial-time perfect matchings in dense hypergraphs
• Powers of tensors and fast matrix multiplication
• Proof of a tiling conjecture of Komlós
• Proof of the Alon-Yuster conjecture
• Refining the graph density condition for the existence of almost \(K\)-factors
• Tiling Turán theorems
• \(F\)-factors in hypergraphs via absorption
• \(H\)-factors in dense graphs

Cited in

(14)

• Denser packings obtained in \(O(n \log \log n)\) time
• An Ore-type theorem for perfect packings in graphs
• On the complexity of digraph packings
• On perfect packings in dense graphs
• scientific article; zbMATH DE number 1229732 (Why is no real title available?)
• The minimum degree threshold for perfect graph packings
• The complexity of generalized clique packing
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
• scientific article; zbMATH DE number 434914 (Why is no real title available?)
• Integer and fractional packings in dense graphs
• The complexity of perfect matchings and packings in dense hypergraphs
• On perfect matchings and tilings in uniform hypergraphs
• The computational complexity of the edge-perfect graph and the totally balanced packing game recognition problems
• Perfect packings with complete graphs minus an edge

This page was built for publication: The complexity of perfect packings in dense graphs

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