A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization

DOI10.1007/s00453-014-9872-xzbMath1328.68151OpenAlexW1999726696WikidataQ59404141 ScholiaQ59404141MaRDI QIDQ494803

Hisao Tamaki, Yasuaki Kobayashi

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9872-x

zbMATH Keywords

graph drawingsubexponential timefixed parameter algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The slotted online one-sided crossing minimization problem on 2-regular graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Edge crossings in drawings of bipartite graphs
• Which problems have strongly exponential complexity?
• On the one-sided crossing minimization in a bipartite graph with large degrees
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• Ranking and Drawing in Subexponential Time
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Fast FAST
• Reducibility among Combinatorial Problems
• Aggregating inconsistent information
• On the complexity of \(k\)-SAT