Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number
DOI10.1007/s00453-022-01093-wOpenAlexW2908098494MaRDI QIDQ6107892
Meirav Zehavi, Roohani Sharma, Pranabendu Misra, Saket Saurabh
Publication date: 28 June 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-01093-w
optimal linear arrangementdirected feedback arc setdirected cutwidthsub-exponential fixed-parameter tractable algorithmsbounded independence number digraph
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Algorithms in computer science (68Wxx) Combinatorics in computer science (68R05) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Graph theory (05Cxx) Combinatorics (educational aspects) (97K20) Theoretical computer science (educational aspects) (97P20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Edge-disjoint paths in digraphs with bounded independence number
- A well-quasi-order for tournaments
- Tournament pathwidth and topological containment
- Tournament immersion and cutwidth
- Fixed-parameter tractability results for feedback set problems in tournaments
- Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
- Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Fast FAST
- A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
- A 7/3-Approximation for Feedback Vertex Sets in Tournaments
- Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs
- Ranking Tournaments
- Jungles, bundles, and fixed-parameter tractability
- Aggregating inconsistent information
This page was built for publication: Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number
