Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number

DOI10.4230/LIPIcs.FSTTCS.2018.35OpenAlexW2963640800MaRDI QIDQ5090975

Roohani Sharma, Meirav Zehavi, Saket Saurabh, Pranabendu Misra

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9934/pdf/LIPIcs-FSTTCS-2018-35.pdf

zbMATH Keywords

optimal linear arrangementdirected feedback arc setbounded independence ndirected cutwidthsub-exponential fixed-parameter tractable algorithms

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Related Items (1)

On width measures and topological problems on semi-complete digraphs

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