Ranking and Drawing in Subexponential Time

DOI10.1007/978-3-642-19222-7_34zbMath1326.68157OpenAlexW1618150311WikidataQ60488574 ScholiaQ60488574MaRDI QIDQ3000521

Henning Fernau, Daniel Lokshtanov, Fedor V. Fomin, Saket Saurabh, Geevarghese Philip, Matthias Mnich

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_34

zbMATH Keywords

social choice theorygraph drawingparameterized complexitysubexponential-time algorithmsdirected feedback arc setKemeny aggregationone-sided crossing minimization

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) Social choice (91B14)

Related Items (4)

Studies in Computational Aspects of Voting ⋮ An FPT algorithm for bipartite vertex splitting ⋮ A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization ⋮ A linear edge kernel for two-layer crossing minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed parameter algorithms for one-sided crossing minimization revisited
• On the parameterized complexity of layered graph drawing
• Parameterizing above or below guaranteed values
• Voting schemes for which it can be difficult to tell who won the election
• Edge crossings in drawings of bipartite graphs
• Which problems have strongly exponential complexity?
• 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 fixed-parameter approach to 2-layer planarization
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Fixed-Parameter Algorithms for Kemeny Scores
• Fast FAST
• Improved Parameterized Algorithms for the Kemeny Aggregation Problem
• Parameterized complexity: exponential speed-up for planar graph problems
• Subexponential Parameterized Algorithms
• Crossing Minimization in Weighted Bipartite Graphs
• Graph Drawing
• Graph Drawing
• Graph Drawing
• Aggregating inconsistent information

This page was built for publication: Ranking and Drawing in Subexponential Time