A polynomial characterization of some graph partitioning problems (Q1108810)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A polynomial characterization of some graph partitioning problems |
scientific article |
Statements
A polynomial characterization of some graph partitioning problems (English)
0 references
1988
0 references
The uniform partition (UP) and the simple max partition (SMP) problems are NP-complete graph partitioning problems, and polynomial-time algorithms are known for few classes of graphs only. In the present paper, the class of line-graphs is considered and a polynomial algorithm is proposed to solve both problems in this class. When the instance space is extended to digraphs, a characterization is possible which leads to similar results.
0 references
graph partitioning
0 references
line-graphs
0 references
polynomial algorithm
0 references
