Combinatorial and computational aspects of graph packing and graph decomposition

DOI10.1016/j.cosrev.2007.07.002zbMath1302.05149OpenAlexW130689240MaRDI QIDQ458446

Raphael Yuster

Publication date: 7 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2007.07.002

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)

Related Items

The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹 ⋮ Network-Based Dissolution ⋮ A greedy algorithm for the social golfer and the Oberwolfach problem ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Edge decompositions and rooted packings of graphs ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ On asymptotic packing of convex geometric and ordered graphs ⋮ Vertex‐disjoint cycles of the same length in tournaments ⋮ A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs ⋮ A survey on Hamilton cycles in directed graphs ⋮ Kernelization and parameterized algorithms for covering a tree by a set of stars or paths ⋮ Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor ⋮ On generalized Fibonacci numbers and \(k\)-distance \(K_p\)-matchings in graphs ⋮ Vertex-disjoint cycles in regular tournaments ⋮ Unnamed Item ⋮ On König graphs with respect to P4 ⋮ Unnamed Item ⋮ Edge-decompositions of graphs with high minimum degree ⋮ On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem ⋮ The Complexity of Perfect Packings in Dense Graphs ⋮ Edge-decompositions of graphs with high minimum degree ⋮ Transitive triangle tilings in oriented graphs ⋮ Star Partitions of Perfect Graphs ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ Decomposing Cubic Graphs into Connected Subgraphs of Size Three ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ Triangle packings and 1-factors in oriented graphs ⋮ Packing degenerate graphs ⋮ On asymptotic packing of geometric graphs ⋮ Cyclic triangle factors in regular tournaments ⋮ Transitive Tournament Tilings in Oriented Graphs with Large Minimum Total Degree ⋮ Structural Properties of Sparse Graphs ⋮ Network-Based Vertex Dissolution ⋮ Unnamed Item ⋮ \(F\)-factors in hypergraphs via absorption ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs

Cites Work

• Nearly-perfect hypergraph packing is in NC
• Proof of the Erdős-Faudree conjecture on quadrilaterals
• A note on the decomposition of graphs into isomorphic matchings
• On circuits in graphs
• Integer and fractional packings of hypergraphs
• Integer and fractional packings in dense graphs
• Matrix multiplication via arithmetic progressions
• On a packing and covering problem
• Matching theory
• Near perfect coverings in graphs and hypergraphs
• Decomposition of large combinatorial structures
• The chromatic connectivity of graphs
• On maximal independent sets of vertices in claw-free graphs
• Matching and covering the vertices of a random graph by copies of a given graph
• Optimal packings of \(K_4\)'s into a \(K_n\)
• Proof of the Seymour conjecture for large graphs
• A simple algorithm for constructing Szemerédi's regularity partition
• Graph decomposition of slim graphs
• Maximum bounded \(H\)-matching is Max SNP-complete
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Blow-up lemma
• Packing graphs: The packing problem solved
• Packing and decomposition of graphs with trees
• Tiling Turán theorems
• Packing triangles in bounded degree graphs.
• \(H\)-factors in dense graphs
• Perfect packings with complete graphs minus an edge
• Asymptotically optimal \(K_k\)-packings of dense graphs via fractional \(K_k\)-decompositions
• Generalized planar matching
• 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
• Easy problems for tree-decomposable graphs
• Fractional decompositions of dense hypergraphs
• Critical chromatic number and the complexity of perfect packings in graphs
• 2000000 Steiner Triple Systems of Order 19
• 3K2-decomposition of a graph
• The NP-Completeness of Some Edge-Partition Problems
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Tree decomposition of graphs
• An algorithmic version of the blow-up lemma
• The Algorithmic Aspects of the Regularity Lemma
• Threshold Functions for H-factors
• Triangle Factors in Random Graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• An Optimal Algorithm for Checking Regularity
• Perfect matchings in random uniform hypergraphs
• Proof of a tiling conjecture of Komlós
• K₄⁻‐factor in a graph
• Families of Trees Decompose the Random Graph in an Arbitrary Way
• Integer and fractional packing of families of graphs
• Every monotone graph property has a sharp threshold
• The decomposition threshold for bipartite graphs with minimum degree one
• On fractional K‐factors of random graphs
• Paths, Trees, and Flowers
• On the completeness of a generalized matching problem
• On the existence of a factor of degree one of a connected random graph
• On the maximal number of independent circuits in a graph
• The Factorization of Linear Graphs
• Some Theorems on Abstract Graphs
• Proof of the Alon-Yuster conjecture
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Combinatorial and computational aspects of graph packing and graph decomposition