Title
Neki optimizacioni problemi uopštenja bisekcije grafova i povezanosti grafova
Creator
Maksimović, Zoran, 1967-
Copyright date
2016
Object Links
Select license
Autorstvo-Nekomercijalno-Bez prerade 3.0 Srbija (CC BY-NC-ND 3.0)
License description
Dozvoljavate samo preuzimanje i distribuciju dela, ako/dok se pravilno naznačava ime autora, bez ikakvih promena dela i bez prava komercijalnog korišćenja dela. Ova licenca je najstroža CC licenca. Osnovni opis Licence: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/deed.sr_LATN. Sadržaj ugovora u celini: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/legalcode.sr-Latn
Language
Serbian
Cobiss-ID
Inventory ID
D-2949
Theses Type
Doktorska disertacija
description
Datum odbrane: 26.09.2016.
Other responsibilities
mentor
Kratica, Jozef, 1966-
član komisije
Pavlović, Ljiljana, 1954-
član komisije
Stojanović, Boban, 1977-
član komisije
Savić, Aleksandar, 1967-
član komisije
Matić, Dragan.
Academic Expertise
Prirodno-matematičke nauke
Academic Title
-
University
Univerzitet u Kragujevcu
Faculty
Prirodno-matematički fakultet
Publisher
[Z. Maksimović]
Format
VIII, 109 listova
Abstract (sr)
U ovom radu razmatrana su dva uopštenja NP-teškog problema maksimalne bisekcije, gde se umesto težina grana kao realnih brojeva uvodi r-torka pozitivnih realnih brijeva.Prvo uopštenje koje se razmatra je višedimenzionalni problem maksimalne bisekcije na povezane podgrafove gde, pored zahteva prvog uopštenja, postoji zahtev da podgrafovi indukovani particijama skupa čvorova budu povezani. Pored navedenih uopštenja, u radu je razmatran i problem određivanja povezanog podgrafa najveće težine sa čvorovima ograničenog stepena.
Abstract (en)
In this dissertation two generalizations of NP-hard maximum bisection problem,
where wights on edges are r-tuples of positive real numbers instead of real numbers,are considered. The rst generalization is the multidimensional maximum bisection problem, where weight on edges are r-tuples of non-negative real numbers. The second
generalization is the connected multidimensional maximum bisection problem,
with additional condition that subgraphs induced by partitions of vertex set are
connected. Beside aforementioned generalizations, in this dissertation is considered
the maximum degree bounded connected subgraph problem.
Multidimensional maximum bisection problem can be applied in human resource
management. One of the most important aspects is compatibility/incompatibility
between employees that is, by its nature, multidimensional. Each criteria of compatibility
is represented by one coordinate of a vector. The connectedness of subgraphs
(teams) plays important role, because teams should be formed by employees that
had been working together before as much as possible. Another application is in electronic
circuits design. There are certain aspects that can be considered important
such as: interference, current, heat dissipation, etc.
For both proposed generalizations of the maximum bisection problem mixed
integer linear programming formulations are given with proofs of its correctness. For
the maximum degree bounded connected subgraph problem a new mixed integer
linear programming formulation with polynomial number of constraints is given.
Using standard solvers CPLEX and Gurobi, optimal solutions are obtained for all
small-size instances and some medium size instances.
Authors Key words
combinatorial optimization, mixed integer linear programming, metaheuristics, variable
neighborhood search, genetic algorithms, electromagnetism, graph bisection
multidimensional maximum bisection problem, connected multidimensional maximum
bisection problem, maximum degree bounded connected subgraph problem
Classification
519.173
Subject
Teorija grafova
Type
Tekst
Abstract (sr)
U ovom radu razmatrana su dva uopštenja NP-teškog problema maksimalne bisekcije, gde se umesto težina grana kao realnih brojeva uvodi r-torka pozitivnih realnih brijeva.Prvo uopštenje koje se razmatra je višedimenzionalni problem maksimalne bisekcije na povezane podgrafove gde, pored zahteva prvog uopštenja, postoji zahtev da podgrafovi indukovani particijama skupa čvorova budu povezani. Pored navedenih uopštenja, u radu je razmatran i problem određivanja povezanog podgrafa najveće težine sa čvorovima ograničenog stepena.
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.