| Abstrakt: | The {\em antibandwidth} problem for graph $G$ consists of labelling $n$ vertices $v_{i}$ of the graph with distinct integers $f(v_{i})$ in range $[1, n]$ in such manner that value $$min \{|f(v_{i})-f(v_{j})| : (v_{i} v_{j}) \in E(G)\}$$ is maximized over all labellings. The problem was originally introduced like dual variation of well-known {\em bandwidth} problem, but it can be reinterpreted in many ways -- as special multiprocessor scheduling problem , special linear layout problem or variant of obnoxious facility location problem. The {\em antibandwidth} problem is NP-complete, there are very few exact results for nontrivial graph classes and some classes of graphs where time for finding the parameter is polynomially bounded. No general heuristics are known so far. In this paper, we give necessary overview of all fundamental information about the problem and then introduce idea of general heuristic for obtaining constructive lower bounds of {\em antibandwidth} parameter of arbitrary bipartite graphs. We describe some variations in the technique and their influence on the results and efficiency of the algorithm. We give statistical comparison to few known results and analyze reasonability for using proposed heuristic.
|
|---|