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:	Vida?Dujmovic author-information" > author-information__contact u-icon-before" > mailto:vida@cs.mcgill.ca" title=" vida@cs.mcgill.ca" itemprop=" email" data-track=" click" data-track-action=" Email author" data-track-label=" " >Email author,Sue?Whitesides author-information" > author-information__contact u-icon-before" > mailto:sue@cs.mcgill.ca" title=" sue@cs.mcgill.ca" itemprop=" email" data-track=" click" data-track-action=" Email author" data-track-label=" " >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 theproblem: the number of allowed edge crossings.

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