A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
From MaRDI portal
Publication:2032354
DOI10.1007/s00453-021-00806-xOpenAlexW3129041135WikidataQ115606747 ScholiaQ115606747MaRDI QIDQ2032354
Jayakrishnan Madathil, Roohani Sharma, Meirav Zehavi
Publication date: 11 June 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10972/
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- A well-quasi-order for tournaments
- Kernels for feedback arc set in tournaments
- Parameterized graph separation problems
- On the complexity of finding balanced oneway cuts
- Some simplified NP-complete graph problems
- An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- Fixed-parameter tractability results for feedback set problems in tournaments
- On width measures and topological problems on semi-complete digraphs
- Tournament minors
- Graph Theory
- On the Parameterized Complexity of Computing Graph Bisections
- Minimum Bisection Is NP-hard on Unit Disk Graphs
- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
- Fast FAST
- Partitioning Planar Graphs
- Color-coding
- Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs
- Strong immersion is a well‐quasi‐ordering for semicomplete digraphs
- Minimum Bisection Is Fixed-Parameter Tractable
- The bisection width of grid graphs
- Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity
- Parameterized Algorithms
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
