Published in

Elsevier, Theoretical Computer Science, 1(148), p. 93-109, 1995

DOI: 10.1016/0304-3975(95)00057-4

Links

Tools

Export citation

Search in Google Scholar

Restrictions of Graph Partition Problems. Part I

Journal article published in 1995 by Hans L. Bodlaender ORCID, Klaus Jansen
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

In this paper partition problems into k independent sets or cliques of bounded size k′ are analyzed for several classes of graphs. We prove the computational complexity of both problems restricted to cographs, split graphs, bipartite graphs and interval graphs given general or constant k and k′. It is shown, that the assignment problem for operations in a branching flow graph to processors, each with a limit on the number of executable operations, equals the first problem restricted to cographs. In addition a job-assignment problem given intervals for each job and k machines, each executing at most k′ jobs, equals the first problem restricted to interval graphs. It is shown, that both problem are NP-complete.