A Linear Edge Kernel for Two-Layer Crossing Minimization

スポンサーリンク

概要

• 論文の詳細を見る

• We consider a simple generalization of two-layer crossing minimization problem (TLCM) called leafedge-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 2^<O(k log k)>+n^<O(1)> time which improves on the previously best known algorithm with running time 2^<O(k^3)>n.

• 一般社団法人電子情報通信学会の論文
• 2013-05-10

著者

• MARUTA HIROKAZU

  Meiji University

• KOBAYASHI YASUAKI

  Meiji University

• NAKAE YUSUKE

  Business Information Technical Systems

• TAMAKI HISAO

  Meiji University

関連論文

• A Linear Edge Kernel for Two-Layer Crossing Minimization

スポンサーリンク