On width measures and topological problems on semi-complete digraphs
From MaRDI portal
Publication:2312615
DOI10.1016/j.jctb.2019.01.006zbMath1415.05063OpenAlexW2914715258WikidataQ128498261 ScholiaQ128498261MaRDI QIDQ2312615
Michał Pilipczuk, Fedor V. Fomin
Publication date: 17 July 2019
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1956/22270
immersiontournamentpathwidthcutwidthfixed-parameter tractabilitytopological containmentsemi-complete digraph
Related Items (4)
Directed width parameters on semicomplete digraphs ⋮ On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The dag-width of directed graphs
- Edge-disjoint paths in digraphs with bounded independence number
- Disjoint paths in tournaments
- A well-quasi-order for tournaments
- Graph minors. XX: Wagner's conjecture
- Tournament pathwidth and topological containment
- Tournament immersion and cutwidth
- Digraph measures: Kelly decompositions, games, and orderings
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Edge-disjoint in- and out-branchings in tournaments and related path problems
- The directed subgraph homeomorphism problem
- Directed tree-width
- Graph minors. XIII: The disjoint paths problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Tournament minors
- The rank-width of edge-coloured graphs
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Parametrized complexity theory.
- On an elementary proof of some asymptotic formulas in the theory of partitions
- Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
- Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
- Are There Any Good Digraph Width Measures?
- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- On the Pathwidth of Almost Semicomplete Digraphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Fast FAST
- The bandwidth problem for graphs and matrices—a survey
- A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- Nondeterminism within $P^ * $
- Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs
- Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
- Finding topological subgraphs is fixed-parameter tractable
- Cutwidth I: A linear time fixed parameter algorithm
- Digraphs
- Jungles, bundles, and fixed-parameter tractability
This page was built for publication: On width measures and topological problems on semi-complete digraphs
