On the Complexity of General Graph Factor Problems

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)

Cited in

(only showing first 100 items - show all)

Construction of k-matchings in graph products
Minimum codegree threshold for $C_6^3$-factors in 3-uniform hypergraphs
Path cover problems with length cost
On the complexity of a family of generalized matching problems
Path-factors in the square of a tree
The Simple Reachability Problem in Switch Graphs
Chain packing in graphs
Dynamic programming on bipartite tree decompositions
Packing $k$-Matchings and $k$-Critical Graphs
Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
Polynomial cases of graph decomposition: A complete solution of Holyer's problem
Regular packing of rooted hyperforests with root constraints in hypergraphs
Improved Algorithms for Several Parameterized Problems Based on Random Methods
On the complexity of generalized chromatic polynomials
Algorithmic complexity of weakly semiregular partitioning and the representation number
On packing 3-vertex paths in a graph
An improved approximation ratio for the jump number problem on interval orders
Edge decompositions and rooted packings of graphs
Binding number conditions for path-factor uniform graphs
Maximum tree-packing in time $O(n^{5/2})$
Algorithms for finding an independent $\{K_1,K_2\}$-packing of maximum weight in a graph
Partitioning vertices of graphs into paths of the same length
On the complexity of some edge-partition problems for graphs
Exact exponential algorithms for clustering problems
Path factors and parallel knock-out schemes of almost claw-free graphs
Sensor networks and distributed CSP: communication, computation and complexity
Inapproximability of $H$-transversal/packing
The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
An approximation algorithm for maximum $P_{3}$-packing in subcubic graphs
Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
Independent packings in structured graphs
Generalized partitions of graphs
Packings by Complete Bipartite Graphs
On the complexity of list $\mathcal{H}$-packing for sparse graph classes
L(2,1)-labeling of the iterated Mycielski graphs of graphs and some problems related to matching problems
Clique factors in pseudorandom graphs
Approximation algorithms for the k^+-star packing problem
Approximation algorithms for non-sequential star packing problems
Factors in randomly perturbed hypergraphs
A degree sequence Hajnal-Szemerédi theorem
The complexity of dissociation set problems in graphs
A parallel algorithm for the maximum 2-chain edge packing problem
Approximation algorithms and hardness results for the clique packing problem
Towards a solution of the Holyer's problem
Packing problems in edge-colored graphs
Optimal packing of induced stars in a graph
Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
On the tree packing problem
On maximum $P_3$-packing in claw-free subcubic graphs
On the complexity of efficient multi-skilled team composition
An $O^*(1.4366^n)$-time exact algorithm for maximum $P_2$-packing in cubic graphs
XSAT and NAE-SAT of linear CNF classes
Tiling directed graphs with tournaments
A covering problem that is easy for trees but $\mathbf{NP}$-complete for trivalent graphs
On the complexity of digraph packings
On directed versions of the Hajnal-Szemerédi theorem
Embedding clique-factors in graphs with low -independence number
Induced graph packing problems
A new self-stabilizing algorithm for maximal $p$-star decomposition of general graphs
The minimum degree threshold for perfect graph packings
Matching and weighted $P_2$-packing: algorithms and kernels
The superstar packing problem
Packing bipartite graphs with covers of complete bipartite graphs
The complexity of generalized clique packing
Induced packing of odd cycles in planar graphs
On rooted packings, decompositions, and factors of graphs
Quantum error correction in Kitaev's quantum double model for abelian groups
Minimum degree threshold for $H$-factors with high discrepancy
H-factors in graphs with small independence number
Path cover problems with length cost
Graphs with maximal induced matchings of the same size
$P_3$-factors in the square of a tree
A discrepancy version of the Hajnal-Szemerédi theorem
An improved kernelization for $P_{2}$-packing
An extension of matching theory
A $5k$-vertex kernel for $P_2$-packing
On matroids induced by packing subgraphs
Packing paths perfectly
Quantifying hierarchical conflicts in homology statements
A note between transitive C₄-factor and oriented Ramsey number
A greedy algorithm for the social golfer and the Oberwolfach problem
The complexity of perfect matchings and packings in dense hypergraphs
The complexity of perfect packings in dense graphs
Parameterized complexity of $(A,\ell)$-path packing
Edge-disjoint packings of graphs
The three-dimensional stable roommates problem with additively separable preferences
The nonnegative node weight $j$-restricted $k$-matching problems
Hitting meets packing: how hard can it be?
Approximation algorithms for non-sequential star packing problems
On the Weisfeiler-Leman dimension of fractional packing
An improved approximation algorithm for the minimum k-star partition problem
Approximating the directed path partition problem
Parameterized complexity of induced graph matching on claw-free graphs
Finding any given 2‐factor in sparse pseudorandom graphs efficiently
On the number of all substructures containing at most four edges
Packings by cliques and by finite families of graphs
Edge decomposition into isomorphic copies of $sK_{1,2}$ is polynomial
Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
The generalized matcher game
A degree sequence version of the Kühn-Osthus tiling theorem

This page was built for publication: On the Complexity of General Graph Factor Problems

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