Exploring the complexity of layout parameters in tournaments and semi-complete digraphs

DOI10.4230/LIPICS.ICALP.2017.70MaRDI QIDQ5111401zbMATH OpenOpenAlexFDO

Authors Florian Barbero, Christophe Paul, Michał Pilipczuk

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.ICALP.2017.70

zbMATH Keywords

tournamentcutwidthsemi-complete digraphOLA

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Exploring the complexity of layout parameters in tournaments and semicomplete digraphs
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
• On width measures and topological problems on semi-complete digraphs
• On the pathwidth of almost semicomplete digraphs

Cited in

(7)

• Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
• Exploring the complexity of layout parameters in tournaments and semicomplete digraphs
• Tournaments and Semicomplete Digraphs
• Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number
• An iterative procedure for evaluating digraph competitions

This page was built for publication: Exploring the complexity of layout parameters in tournaments and semi-complete digraphs

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