On the Complexity of General Graph Factor Problems

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(only showing first 100 items - show all)

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
A surprising permanence of old motivations (a not-so-rigid story)
Edge decompositions into two kinds of graphs
An extension of matching theory
On the complexity of a family of generalized matching problems
Packings by cliques and by finite families of graphs
The complexity of generalized clique packing
On matroids induced by packing subgraphs
A parallel algorithm for the maximum 2-chain edge packing problem
On the tree packing problem
Generalized partitions of graphs
Edge-disjoint packings of graphs
Packing problems in edge-colored graphs
Edge decomposition into isomorphic copies of $sK_{1,2}$ is polynomial
Optimal packing of induced stars in a graph
Maximum tree-packing in time $O(n^{5/2})$
On the complexity of some edge-partition problems for graphs
On maximum $P_3$-packing in claw-free subcubic graphs
Parameterized complexity of $(A,\ell)$-path packing
A $5k$-vertex kernel for $P_2$-packing
The superstar packing problem
The minimum degree threshold for perfect graph packings
Path cover problems with length cost
Quantifying hierarchical conflicts in homology statements
A degree sequence version of the Kühn-Osthus tiling theorem
The complexity of dissociation set problems in graphs
The complexity of perfect matchings and packings in dense hypergraphs
A new self-stabilizing algorithm for maximal $p$-star decomposition of general graphs
XSAT and NAE-SAT of linear CNF classes
Packing bipartite graphs with covers of complete bipartite graphs
Sensor networks and distributed CSP: communication, computation and complexity
A degree sequence Hajnal-Szemerédi theorem
Independent packings in structured graphs
Dealing with several parameterized problems by random methods
$P_3$-factors in the square of a tree
A greedy algorithm for the social golfer and the Oberwolfach problem
The three-dimensional stable roommates problem with additively separable preferences
Edge decompositions and rooted packings of graphs
On packing 3-vertex paths in a graph
The complexity of perfect packings in dense graphs
An $O^*(1.4366^n)$-time exact algorithm for maximum $P_2$-packing in cubic graphs
Tiling directed graphs with tournaments
Graphs with maximal induced matchings of the same size
The Simple Reachability Problem in Switch Graphs
Packings by Complete Bipartite Graphs
An improved approximation ratio for the jump number problem on interval orders
Matching and weighted $P_2$-packing: algorithms and kernels
Packing $k$-Matchings and $k$-Critical Graphs
Improved algorithms for several parameterized problems based on random methods
Algorithms for finding an independent $\{K_1,K_2\}$-packing of maximum weight in a graph
Parameterized complexity of induced graph matching on claw-free graphs
A discrepancy version of the Hajnal-Szemerédi theorem
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
Construction of k-matchings in graph products
Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
The nonnegative node weight $j$-restricted $k$-matching problems
An asymptotic multipartite Kühn-Osthus theorem
Algorithmic complexity of weakly semiregular partitioning and the representation number
Inapproximability of $H$-transversal/packing
On directed versions of the Hajnal-Szemerédi theorem
Minimum codegree threshold for $C_6^3$-factors in 3-uniform hypergraphs
On rooted packings, decompositions, and factors of graphs
Approximation algorithms and hardness results for the clique packing problem
On the Weisfeiler-Leman dimension of fractional packing
Embedding clique-factors in graphs with low -independence number
Induced graph packing problems
Finding any given 2‐factor in sparse pseudorandom graphs efficiently
Path cover problems with length cost
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
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
Approximating the directed path partition problem
Packing K_rs in bounded degree graphs
On the complexity of list $\mathcal{H}$-packing for sparse graph classes
Minimum degree threshold for $H$-factors with high discrepancy
H-factors in graphs with small independence number
The maximum 3-star packing problem in claw-free cubic graphs
Degree conditions for path-factors in graphs
On the complexity of generalized chromatic polynomials
A note between transitive C₄-factor and oriented Ramsey number
Approximation algorithms for non-sequential star packing problems
An improved approximation algorithm for the minimum k-star partition problem
Dynamic programming on bipartite tree decompositions
Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
Dynamic programming on bipartite tree decompositions
On the complexity of list $\mathcal{H}$-packing for sparse graph classes
Regular packing of rooted hyperforests with root constraints in hypergraphs
Binding number conditions for path-factor uniform graphs
Partitioning vertices of graphs into paths of the same length
Exact exponential algorithms for clustering problems
L(2,1)-labeling of the iterated Mycielski graphs of graphs and some problems related to matching problems

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)