The complexity of perfect packings in dense graphs
DOI10.1007/978-3-319-55911-7_21zbMATH Open1485.68185OpenAlexW2602033211MaRDI QIDQ2988829FDOQ2988829
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
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
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)
Cites Work
- Powers of tensors and fast matrix multiplication
- Tiling Turán theorems
- \(H\)-factors in dense graphs
- \(F\)-factors in hypergraphs via absorption
- On extremal problems of graphs and generalized graphs
- On the Complexity of General Graph Factor Problems
- A Dirac-Type Theorem for 3-Uniform Hypergraphs
- Paths, Trees, and Flowers
- Proof of the Alon-Yuster conjecture
- A geometric theory for hypergraph matching
- Maximum bounded \(H\)-matching is Max SNP-complete
- 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
- Combinatorial and computational aspects of graph packing and graph decomposition
- Perfect packings with complete graphs minus an edge
- Refining the graph density condition for the existence of almost \(K\)-factors
- Critical chromatic number and the complexity of perfect packings in graphs
- Proof of a tiling conjecture of Komlós
- K4−‐factor in a graph
- Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
- Computational complexity of the perfect matching problem in hypergraphs with subcritical density
- Polynomial-time perfect matchings in dense hypergraphs
Cited In (14)
- Denser packings obtained in \(O(n \log \log n)\) time
- An Ore-type theorem for perfect packings in graphs
- On perfect packings in dense graphs
- On the complexity of digraph packings
- Title not available (Why is that?)
- The minimum degree threshold for perfect graph packings
- The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
- The complexity of generalized clique packing
- Title not available (Why is that?)
- 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)
