Exact Algorithms for MaxCut on Split Graphs

2024/05/31 by Marko Lalovic, Lalovic, Marko · 1 citation
Computer Science · #05C85 (Primary) 68R10 #68W05 (Secondary) #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Graph Labeling and Dimension Problems #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2405.20599

openalex publication_date 2024/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper presents an O^*(1.42ⁿ) time algorithm for the Maximum Cut problem on split graphs, along with a subexponential time algorithm for its decision variant.

Cited by

• Probabilistic Computing Optimization of Complex Spin-Glass Topologies

Related

• Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
• Near-optimal approximation algorithm for simultaneous Max-Cut
• A linear time algorithm for a variant of the max cut problem in series parallel graphs
• Solving Cut-Problems in Quadratic Time for Graphs With Bounded Treewidth
• An approximation algorithm for Maximum DiCut vs. Cut