Show simple item record

dc.contributor.advisorKratica, Jozef
dc.contributor.otherPavlović, Ljiljana
dc.contributor.otherStojanović, Boban
dc.contributor.otherSavić, Aleksandar
dc.contributor.otherMatić, Dragan.
dc.creatorMaksimović, Zoran
dc.date.accessioned2016-10-22T10:05:55Z
dc.date.available2016-10-22T10:05:55Z
dc.date.available2020-07-03T15:07:43Z
dc.date.issued2016-09-26
dc.identifier.urihttp://eteze.kg.ac.rs/application/showtheses?thesesId=4061
dc.identifier.urihttp://nardus.mpn.gov.rs/handle/123456789/6853
dc.identifier.urihttps://fedorakg.kg.ac.rs/fedora/get/o:690/bdef:Content/download
dc.description.abstractU 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.abstractIn 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.formatapplication/pdf
dc.languagesr
dc.publisherУниверзитет у Крагујевцу, Природно-математички факултетsr
dc.rightsopenAccessen
dc.sourceУниверзитет у Крагујевцуsr
dc.subjectcombinatorial optimizationen
dc.subjectmixed integer linear programmingen
dc.subjectmetaheuristicsen
dc.subjectvariable neighborhood searchen
dc.subjectgenetic algorithmsen
dc.subjectelectromagnetismen
dc.subjectgraph bisection multidimensional maximum bisection problemen
dc.subjectconnected multidimensional maximum bisection problemen
dc.subjectmaximum degree bounded connected subgraph problemen
dc.titleNeki optimizacioni problemi uopštenja bisekcije grafova i povezanosti grafovasr
dc.typedoctoralThesisen
dc.rights.licenseBY-NC-ND
dcterms.abstractКратица, Јозеф; Павловић, Љиљана; Матић, Драган.; Савић, Aлександар; Стојановић, Бобан; Максимовић, Зоран; Неки оптимизациони проблеми уопштења бисекције графова и повезаности графова; Неки оптимизациони проблеми уопштења бисекције графова и повезаности графова;
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/47302/Disertacija5066.pdf
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/47303/izvestaj_Zoran_Maksimovic_PMF.pdf


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record