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

DOI10.4230/LIPICS.FSTTCS.2018.35MaRDI QIDQ5090975zbMATH OpenOpenAlexFDO

Authors Pranabendu Misra, Saket Saurabh, Roohani Sharma, Meirav Zehavi

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)

Recommendations

• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• Exploring the complexity of layout parameters in tournaments and semicomplete digraphs

Cites work

• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• A 7/3-approximation for feedback vertex sets in tournaments
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• A well-quasi-order for tournaments
• Aggregating inconsistent information: ranking and clustering
• Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
• Edge-disjoint paths in digraphs with bounded independence number
• Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
• Fast FAST
• Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
• Faster exact and parameterized algorithm for feedback vertex set in tournaments
• Fixed-parameter tractability results for feedback set problems in tournaments
• Jungles, bundles, and fixed-parameter tractability
• Ranking Tournaments
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Tournament immersion and cutwidth
• Tournament pathwidth and topological containment

Cited in

(1)

• On width measures and topological problems on semi-complete digraphs

This page was built for publication: Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number

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