Neki optimizacioni problemi uopštenja bisekcije grafova i povezanosti grafova
Author
Maksimović, ZoranMentor
Kratica, JozefCommittee members
Pavlović, LjiljanaStojanović, Boban
Savić, Aleksandar
Matić, Dragan
Metadata
Show full item recordAbstract
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.
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.