The Complexity of Perfect Packings in Dense Graphs
From MaRDI portal
Publication:2988829
DOI10.1007/978-3-319-55911-7_21zbMath1485.68185OpenAlexW2602033211MaRDI QIDQ2988829
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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)
Related Items (2)
On Perfect Matchings and Tilings in Uniform Hypergraphs ⋮ The complexity of perfect matchings and packings in dense hypergraphs
Cites Work
- Unnamed Item
- Combinatorial and computational aspects of graph packing and graph decomposition
- Polynomial-time perfect matchings in dense hypergraphs
- Maximum bounded \(H\)-matching is Max SNP-complete
- Tiling Turán theorems
- \(H\)-factors in dense graphs
- \(F\)-factors in hypergraphs via absorption
- On extremal problems of graphs and generalized graphs
- Perfect packings with complete graphs minus an edge
- Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs
- On the Complexity of General Graph Factor Problems
- COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY
- 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
- A Dirac-Type Theorem for 3-Uniform Hypergraphs
- Powers of tensors and fast matrix multiplication
- Critical chromatic number and the complexity of perfect packings in graphs
- Proof of a tiling conjecture of Komlós
- K4−‐factor in a graph
- Paths, Trees, and Flowers
- A geometric theory for hypergraph matching
- Proof of the Alon-Yuster conjecture
This page was built for publication: The Complexity of Perfect Packings in Dense Graphs