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

absorbing methodcomputational complexityperfect packing

Mathematics Subject Classification ID

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

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
• \(F\)-factors in hypergraphs via absorption
• \(H\)-factors in dense graphs
• 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

Cited in

(15)

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

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)