An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization

Authors:	Email author" target="_blank">Vida?Dujmovic Email author Email author" target="_blank">Sue?Whitesides Email author

Affiliation:	(1) School of Computer Science, McGill University, 3480 University Street, Montreal, Québec, H3A 2A7, Canada

Abstract:	We give an O(^k · n²) fixed parameter tractable algorithm for the 1-Sided Crossing Minimization. The constant in the running time is the golden ratio = (1+5)/2 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.

Keywords:	Graph drawing FPT Fixed parameter tractability Sided crossing minimization Layer crossing minimization NP-completeness Layer drawings Level drawings
本文献已被 SpringerLink 等数据库收录！