Kobayashi Y.,Meiji University |
Maruta H.,Meiji University |
Nakae Y.,Business Information Technical Systems |
Tamaki H.,Meiji University
Theoretical Computer Science | Year: 2014
The two-layer crossing minimization problem (TLCM), given a bipartite graph G with n vertices and a positive integer k, asks whether G has a two-layer drawing with at most k crossings. We consider a simple generalization of TLCM called leaf-edge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with O(k) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2O(klogk)+nO(1) time which improves on the previously best known algorithm with running time 2O(k3)n. © 2014 Elsevier B.V.