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

DOI10.4230/LIPICS.FSTTCS.2018.35OpenAlexW2963640800MaRDI QIDQ5090975FDOQ5090975

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)

Cites Work

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

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)