A rearrangement of adjacency matrix based approach for solving the crossing minimization problem |
| |
Authors: | Neng Fan Panos M Pardalos |
| |
Institution: | (1) Carnegie Mellon University, Pittsburgh, PA, 15213, USA;(2) IBM TJ. Watson, Hawthorne, NY, USA;(3) Department of Computer Science, University of Illinois at Chicago, Chicago, IL, USA |
| |
Abstract: | In this paper, we first present a binary linear programming formulation for the crossing minimization problem (CMP) in bipartite
graphs. Then we use the models of a modified minimum cost flow problem (MMCF) and a travelling salesman problem (TSP) to approximatively
solve the CMP by rearranging the adjacency matrix of the bipartite graph. Our approaches are useful for problems defined on
dense bipartite graphs. In addition, we compute the exact crossing numbers for some general dense graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|