A polynomial characterization of some graph partitioning problems (Q1108810)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A polynomial characterization of some graph partitioning problems |
scientific article; zbMATH DE number 4068323
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A polynomial characterization of some graph partitioning problems |
scientific article; zbMATH DE number 4068323 |
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
