• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Master theses
  • Vis innførsel
  •   Hjem
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Master theses
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

Kernelization for Balanced Graph Clustering

Steinvik, Andreas
Master thesis
Thumbnail
Åpne
master thesis (558.4Kb)
Permanent lenke
https://hdl.handle.net/1956/24115
Utgivelsesdato
2020-10-03
Metadata
Vis full innførsel
Samlinger
  • Master theses [40]
Sammendrag
The problems of Balanced Graph Clustering ask whether it is possible to modify a graph such that it becomes a cluster graph where no cluster has a size larger than a given multiplicative factor or absolute difference relative to any other cluster in the graph, by at most k graph modifications. In this thesis we study the problems with respect to the graph modification operations vertex deletion, edge addition and edge deletion. We will show NP-completeness and give polynomial kernels for each version.
Utgiver
The University of Bergen
Opphavsrett
Copyright the Author. All rights reserved

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit
 

 

Bla i

Hele arkivetDelarkiv og samlingerUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifterDenne samlingenUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifter

Min side

Logg inn

Statistikk

Besøksstatistikk

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit