A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
From MaRDI portal
Publication:494803
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
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
