A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
type: Item
instance of: scholarly article
title: A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
author: Jayakrishnan Madathil
author: Roohani Sharma
author: Meirav Zehavi
published in: Algorithmica
publication date: 2021-06-11T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10972/
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7357821
zbMATH Keywords: bisection
zbMATH Keywords: semicomplete digraph
zbMATH Keywords: tournament
zbMATH Keywords: FPT algorithm
zbMATH Keywords: chromatic coding
zbMATH Keywords: polynomial kernel
zbMATH Keywords: splitters
MaRDI profile type: Publication
Wikidata QID: Q115606747
OpenAlex ID: W3129041135
cites work: Fast FAST
cites work: Color-coding
cites work: Q4539516
cites work: Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs
cites work: Strong immersion is a well‐quasi‐ordering for semicomplete digraphs
cites work: Kernels for feedback arc set in tournaments
cites work: Partitioning Planar Graphs
cites work: Q3267901
cites work: A well-quasi-order for tournaments
cites work: Parameterized Algorithms
cites work: Minimum Bisection Is Fixed-Parameter Tractable
cites work: Minimum Bisection Is NP-hard on Unit Disk Graphs
cites work: Graph Theory
cites work: Fixed-parameter tractability results for feedback set problems in tournaments
cites work: On the complexity of finding balanced oneway cuts
cites work: An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs
cites work: On width measures and topological problems on semi-complete digraphs
cites work: Some simplified NP-complete graph problems
cites work: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
cites work: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
cites work: Tournament minors
cites work: On the algorithmic effectiveness of digraph decompositions and complexity measures
cites work: Q5092387
cites work: Parameterized graph separation problems
cites work: Q4231923
cites work: Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity
cites work: The bisection width of grid graphs
cites work: Q3549709
cites work: Q4756732
cites work: On the Parameterized Complexity of Computing Graph Bisections
DOI: 10.1007/S00453-021-00806-X
description: scientific article; zbMATH DE number 7357821