Neki optimizacioni problemi uopštenja bisekcije grafova i povezanosti grafova

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.

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.