Posplošena električna dominacija

diplomsko delo

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

Abstract

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.

Keywords

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;

Data

Language:	Slovenian
Year of publishing:	2014
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[A. Omerzel]
UDC:	004.021:537(043.2)
COBISS:	10783828
Views:	0
Downloads:	0
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Generalized Power Domination
Secondary abstract:	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.
Secondary keywords:	power domination;general power domination;tree;Java;NP-complete problem;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
File type:	application/pdf
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Thesis comment:	Univerza v Ljubljani, Fak. za računalništvo in informatiko
Pages:	45 str.
ID:	8739363