Posplošena električna dominacija

diplomsko delo

Aleš Omerzel (Avtor), Sandi Klavžar (Mentor)

Povzetek

Problem električne dominacije je optimizacijski problem, ki se je pojavil v novodobnem času skupaj z razvojem električnih omrežij. V električnem omrežju je potrebno nadzorovati tok in napetost na vseh stičiščih in povezavah. Merilne naprave so drage, zato vlada težnja h postaviti najmanjšega števila naprav tako, da bi omrežje ostalo v celoti nadzorovano. Problem električne dominacije se posploši na problem k-električne dominacije. V diplomski nalogi so z definicijo obeh problemov predstavljena pravila za širjenje nadzora v omrežju. Za tem je podan in dokazan linearen algoritem za iskanje optimalne k-električne dominantne množice na drevesih. Sledi implementacija algoritma v programskem jeziku Java. V zaključku pa je dokazana NP-polnost problema električne dominacije na dvodelnih grafih.

Ključne besede

električna dominacija;posplošena električna dominacija;drevo;Java;NP-poln problem;računalništvo;računalništvo in informatika;računalništvo in matematika;univerzitetni študij;interdisciplinarni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2014
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[A. Omerzel]
UDK:	004.021:537(043.2)
COBISS:	10783828
Št. ogledov:	0
Št. prenosov:	0
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Generalized Power Domination
Sekundarni povzetek:	The power domination problem is an optimization problem that has emerged together with the development of the power networks. It is important to control the voltage and current in all the nodes and links in a power network. Measuring devices are expensive, which is why there is a tendency to place a minimum number of devices in a power network so that the network remains fully supervised. The k-power domination is a generalization of the power domination. The thesis represents the rules of the dissemination of the control in the network. A linear algorithm is provided for finding the optimal k-power dominating set on trees and followed by the implementation of the algorithm in Java. At the end NP-completeness for the power domination problem on bipartite graphs is proved.
Sekundarne ključne besede:	power domination;general power domination;tree;Java;NP-complete problem;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Komentar na gradivo:	Univerza v Ljubljani, Fak. za računalništvo in informatiko
Strani:	45 str.
ID:	8739363