On the Complexity of General Graph Factor Problems
From MaRDI portal
Publication:3038617
DOI10.1137/0212040zbMath0525.68023OpenAlexW1999341643MaRDI QIDQ3038617
Pavol Hell, David G. Kirkpatrick
Publication date: 1983
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0212040
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)
Related Items (93)
An Asymptotic Multipartite Kühn--Osthus Theorem ⋮ Edge-disjoint packings of graphs ⋮ Packing problems in edge-colored graphs ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ On the Number of All Substructures Containing at Most Four Edges ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs ⋮ Construction of k-matchings in graph products ⋮ Dealing with several parameterized problems by random methods ⋮ Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial ⋮ The superstar packing problem ⋮ The minimum degree threshold for perfect graph packings ⋮ Packings by Complete Bipartite Graphs ⋮ Path cover problems with length cost ⋮ Unnamed Item ⋮ On matroids induced by packing subgraphs ⋮ Graphs with maximal induced matchings of the same size ⋮ Optimal packing of induced stars in a graph ⋮ Quantifying hierarchical conflicts in homology statements ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ \(P_3\)-factors in the square of a tree ⋮ A parallel algorithm for the maximum 2-chain edge packing problem ⋮ Induced graph packing problems ⋮ On the complexity of some edge-partition problems for graphs ⋮ Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis ⋮ A greedy algorithm for the social golfer and the Oberwolfach problem ⋮ The three-dimensional stable roommates problem with additively separable preferences ⋮ An improved approximation ratio for the jump number problem on interval orders ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ Maximum tree-packing in time \(O(n^{5/2})\) ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Embedding clique-factors in graphs with low \(\ell\)-independence number ⋮ Edge decompositions and rooted packings of graphs ⋮ Finding any given 2‐factor in sparse pseudorandom graphs efficiently ⋮ On packing 3-vertex paths in a graph ⋮ Factors in randomly perturbed hypergraphs ⋮ Maximum tree-packing in time O(n5/2) ⋮ Packing 2- and 3-stars into cubic graphs ⋮ \(P_k\)-factors in squares and line graphs of trees ⋮ On the complexity of efficient multi-skilled team composition ⋮ A degree sequence version of the Kühn-Osthus tiling theorem ⋮ Towards a solution of the Holyer's problem ⋮ The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices ⋮ Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube ⋮ Packing $k$-Matchings and $k$-Critical Graphs ⋮ Approximating the directed path partition problem ⋮ On Directed Versions of the Hajnal–Szemerédi Theorem ⋮ Minimum Codegree Threshold forC63-Factors in 3-Uniform Hypergraphs ⋮ XSAT and NAE-SAT of linear CNF classes ⋮ Packing bipartite graphs with covers of complete bipartite graphs ⋮ The Complexity of Perfect Packings in Dense Graphs ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ Sensor networks and distributed CSP: communication, computation and complexity ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Path-factors in the square of a tree ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ On the tree packing problem ⋮ On the complexity of generalized chromatic polynomials ⋮ Approximation algorithms and hardness results for the clique packing problem ⋮ Algorithmic complexity of weakly semiregular partitioning and the representation number ⋮ Star Partitions of Perfect Graphs ⋮ On Rooted Packings, Decompositions, and Factors of Graphs ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Path factors and parallel knock-out schemes of almost claw-free graphs ⋮ Path cover problems with length cost ⋮ The Simple Reachability Problem in Switch Graphs ⋮ The complexity of dissociation set problems in graphs ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ An improved kernelization for \(P_{2}\)-packing ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ A covering problem that is easy for trees but \(\mathbf{NP}\)-complete for trivalent graphs ⋮ On the complexity of digraph packings ⋮ Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph ⋮ Polynomial cases of graph decomposition: A complete solution of Holyer's problem ⋮ Packing paths perfectly ⋮ Induced packing of odd cycles in planar graphs ⋮ Generalized partitions of graphs ⋮ A discrepancy version of the Hajnal–Szemerédi theorem ⋮ The generalized matcher game ⋮ The Nonnegative Node Weight j-Restricted k-Matching Problems ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Edge decompositions into two kinds of graphs ⋮ TILING DIRECTED GRAPHS WITH TOURNAMENTS ⋮ An extension of matching theory ⋮ Independent packings in structured graphs ⋮ Chain packing in graphs ⋮ On the complexity of a family of generalized matching problems ⋮ Packings by cliques and by finite families of graphs ⋮ A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs ⋮ The complexity of generalized clique packing ⋮ A degree sequence Hajnal-Szemerédi theorem ⋮ Parameterized complexity of \((A,\ell)\)-path packing ⋮ A \(5k\)-vertex kernel for \(P_2\)-packing
This page was built for publication: On the Complexity of General Graph Factor Problems
