On the complexity of some edge-partition problems for graphs (Q1923590): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 15:49, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the complexity of some edge-partition problems for graphs |
scientific article |
Statements
On the complexity of some edge-partition problems for graphs (English)
0 references
9 October 1996
0 references
Let \(F\) be a family of graphs. An \(F\)-decomposition of a graph \(G\) is a partition of the edge set of \(G\) into subgraphs isomorphic to members of \(F\). The paper concentrates on some complexity problems concerning \(F\)-decompositions. It is shown that if \(F\) contains neither the 1-edge nor the 2-edge star, it is NP-complete to decide whether a bipartite graph admits an \(F\)-decomposition, thereby strengthening a result of P. Hell and D. G. Kirkpatrick on partitioning the node set of a graph into complete graphs of certain orders. If \(F\) contains a 2-edge star, it yields a good characterization of graphs, not necessarily bipartite, that admit \(F\)-decompositions. This characterization gives a linear time algorithm for constructing such a decomposition, if one exists.
0 references
partition
0 references
complexity
0 references
NP-complete
0 references
characterization
0 references
linear time algorithm
0 references
decomposition
0 references