On the complexity of some edge-partition problems for graphs (Q1923590): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3999150 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3915022 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: NP-completeness of graph decomposition problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge-disjoint packings of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Packing subgraphs in a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Complexity of General Graph Factor Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Packings by cliques and by finite families of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Packings by Complete Bipartite Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs with 1-Factors / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:05, 24 May 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