Published in

Elsevier, Discrete Applied Mathematics, 1-3(62), p. 119-130, 1995

DOI: 10.1016/0166-218x(94)00149-8

Links

Tools

Export citation

Search in Google Scholar

On some algorithmic investigations of star partitions of graphs

Journal article published in 1995 by Dragos̆ Cvetković, Peter Rowlinson, Slobodan Simić
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

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.