Приказ основних података о дисертацији
Neki optimizacioni problemi uopštenja bisekcije grafova i povezanosti grafova
dc.contributor.advisor | Kratica, Jozef | |
dc.contributor.other | Pavlović, Ljiljana | |
dc.contributor.other | Stojanović, Boban | |
dc.contributor.other | Savić, Aleksandar | |
dc.contributor.other | Matić, Dragan | |
dc.creator | Maksimović, Zoran | |
dc.date.accessioned | 2016-10-22T10:05:55Z | |
dc.date.available | 2016-10-22T10:05:55Z | |
dc.date.available | 2020-07-03T15:07:43Z | |
dc.date.issued | 2016-09-26 | |
dc.identifier.uri | http://eteze.kg.ac.rs/application/showtheses?thesesId=4061 | |
dc.identifier.uri | https://nardus.mpn.gov.rs/handle/123456789/6853 | |
dc.identifier.uri | https://fedorakg.kg.ac.rs/fedora/get/o:690/bdef:Content/download | |
dc.description.abstract | 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. | sr |
dc.description.abstract | 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. | en |
dc.format | application/pdf | |
dc.language | sr | |
dc.publisher | Универзитет у Крагујевцу, Природно-математички факултет | sr |
dc.rights | openAccess | en |
dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/ | |
dc.source | Универзитет у Крагујевцу | sr |
dc.subject | combinatorial optimization | en |
dc.subject | mixed integer linear programming | en |
dc.subject | metaheuristics | en |
dc.subject | variable neighborhood search | en |
dc.subject | genetic algorithms | en |
dc.subject | electromagnetism | en |
dc.subject | graph bisection multidimensional maximum bisection problem | en |
dc.subject | connected multidimensional maximum bisection problem | en |
dc.subject | maximum degree bounded connected subgraph problem | en |
dc.title | Neki optimizacioni problemi uopštenja bisekcije grafova i povezanosti grafova | sr |
dc.type | doctoralThesis | en |
dc.rights.license | BY-NC-ND | |
dcterms.abstract | Кратица, Јозеф; Павловић, Љиљана; Матић, Драган.; Савић, Aлександар; Стојановић, Бобан; Максимовић, Зоран; Неки оптимизациони проблеми уопштења бисекције графова и повезаности графова; Неки оптимизациони проблеми уопштења бисекције графова и повезаности графова; | |
dc.identifier.fulltext | http://nardus.mpn.gov.rs/bitstream/id/47302/Disertacija5066.pdf | |
dc.identifier.fulltext | http://nardus.mpn.gov.rs/bitstream/id/47303/izvestaj_Zoran_Maksimovic_PMF.pdf | |
dc.identifier.fulltext | https://nardus.mpn.gov.rs/bitstream/id/47302/Disertacija5066.pdf | |
dc.identifier.fulltext | https://nardus.mpn.gov.rs/bitstream/id/47303/izvestaj_Zoran_Maksimovic_PMF.pdf | |
dc.identifier.rcub | https://hdl.handle.net/21.15107/rcub_nardus_6853 |