Combinatorial and computational aspects of graph packing and graph decomposition

DOI10.1016/J.COSREV.2007.07.002zbMATH Open1302.05149OpenAlexW130689240MaRDI QIDQ458446FDOQ458446

Authors: 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

Recommendations

• Extremal aspects of graph and hypergraph decomposition problems
• Packing of graphs - a survey
• Edge decompositions and rooted packings of graphs
• scientific article; zbMATH DE number 1156583
• Graph packings

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (41)

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

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

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