Characterization of the Imbalance Problem on Complete Bipartite Graphs

10/30/2021
by   Steven Ge, et al.
0

We study the imbalance problem on complete bipartite graphs. The imbalance problem is a graph layout problem and is known to be NP-complete. Graph layout problems find their applications in the optimization of networks for parallel computer architectures, VLSI circuit design, information retrieval, numerical analysis, computational biology, graph theory, scheduling and archaeology. In this paper, we give characterizations for the optimal solutions of the imbalance problem on complete bipartite graphs. Using the characterizations, we can solve the imbalance problem in 𝒪(log(|V|) ·log(log(|V|))) time, when given the cardinalities of the parts of the graph, and verify whether a given solution is optimal in O(|V|) time on complete bipartite graphs. We also introduce a restricted form of proper interval bipartite graphs on which the imbalance problem is solvable in 𝒪(c ·log(|V|) ·log(log(|V|))) time, where c = 𝒪(|V|), by using the aforementioned characterizations.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset