Abstract
This paper presents an $O^{*}(1.42^{n})$ time algorithm for the Maximum Cut problem on split graphs, along with a subexponential time algorithm for its decision variant.
Exact Algorithms for MaxCut on Split Graphs
Related papers
Ranked by semantic similarity β how closely each paper's abstract matches this one (100% = near-identical topic).
- Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson (2025)69% match
- Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries (2024)69% match
- Faster exponential algorithms for cut problems via geometric data structures (2025)68% match
- Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-TurzΓk Bound (2024)67% match
- Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs (2025)65% match
- Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs (2025)63% match
- Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach (2025)63% match
- Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs (2024)63% match