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

DOI10.1007/S00453-014-9872-XMaRDI QIDQ494803zbMATH OpenOpenAlexWikidataFDO

Authors Yasuaki Kobayashi, Hisao Tamaki

Publication date 2 September 2015

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

subexponential timegraph drawingfixed parameter algorithm

Mathematics Subject Classification ID

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

Recommendations

• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• scientific article; zbMATH DE number 1974113
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Graph Drawing

Cites work

• scientific article; zbMATH DE number 2084271 (Why is no real title available?)
• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• Aggregating inconsistent information: ranking and clustering
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• Edge crossings in drawings of bipartite graphs
• Fast FAST
• Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Lower bounds based on the exponential time hypothesis
• On the complexity of \(k\)-SAT
• On the one-sided crossing minimization in a bipartite graph with large degrees
• Ranking and drawing in subexponential time
• Reducibility among combinatorial problems
• Which problems have strongly exponential complexity?

Cited in

(8)

• scientific article; zbMATH DE number 1974113 (Why is no real title available?)
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• A survey of parameterized algorithms and the complexity of edge modification
• The slotted online one-sided crossing minimization problem on 2-regular graphs
• Parameterized analysis and crossing minimization problems
• Graph Drawing
• Fixed parameter algorithms for one-sided crossing minimization revisited
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation

This page was built for publication: A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494803)