Skip header navigation
×

Article

On some algorithmic investigations of star partitions of graphs

Citation
Cvetkovic D, Rowlinson P & Simic S (1995) On some algorithmic investigations of star partitions of graphs. Discrete Applied Mathematics, 62 (1-3), pp. 119-130. https://doi.org/10.1016/0166-218X%2894%2900149-8

Abstract
Star partitions of graphs were introduced in a recent paper by the same authors in order to extend spectral methods in algebraic graph theory. Here it is shown that the corresponding partitioning problem is polynomial. Two algorithms are investigated: the first is based on the maximum matching problem for graphs, and the second invokes an algorithm for matroid intersection.

Journal
Discrete Applied Mathematics: Volume 62, Issue 1-3

StatusPublished
Author(s)Cvetkovic, Dragos; Rowlinson, Peter; Simic, Slobodan
Publication date08/09/1995
PublisherElsevier
ISSN0166-218X
Scroll back to the top