Cover Image

Exact Algorithms for MaxCut on Split Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Lalovic, Marko
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms 05C85 (Primary) 68R10, 68W05 (Secondary) F.2.2; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

A $4/3$ Approximation for $2$-Vertex-Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2023)

Shortest two disjoint paths in conservative graphs
by: Schlotter, Ildikó
Published: (2023)

Traffic-Oblivious Multi-Commodity Flow Network Design
by: Chimani, Markus, et al.
Published: (2025)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

A Constant-factor Approximation for Weighted Bond Cover
by: Kim, Eun Jung, et al.
Published: (2021)

Low Recourse Arborescence Forests Under Uniformly Random Arcs
by: Dahlmeier, J Niklas, et al.
Published: (2025)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
by: Krishnaswamy, Ravishankar, et al.
Published: (2014)

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
by: Chimani, Markus, et al.
Published: (2023)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Identification to Subclasses of Chordal Graphs
by: Golovach, Petr A., et al.
Published: (2026)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
by: Atherton, William, et al.
Published: (2024)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
by: Haslebacher, Sebastian
Published: (2025)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
by: Patzner, Julian, et al.
Published: (2024)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

Fast FPT Algorithms for Grundy Number on Dense Graphs
by: Nezhad, Sina Ghasemi, et al.
Published: (2024)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
by: Buchbinder, Niv, et al.
Published: (2024)

Designing Capacitated Subnetworks for Shortest Path Routing
by: Chimani, Markus, et al.
Published: (2026)

On the Average-Case Performance of Greedy for Maximum Coverage
by: Balkanski, Eric, et al.
Published: (2026)

Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
by: Gabryelski, Wojciech, et al.
Published: (2026)

Graph modification of bounded size to minor-closed classes as fast as vertex deletion
by: Morelle, Laure, et al.
Published: (2025)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
by: Huber, Michael Kiran
Published: (2024)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

Dynamic programming on bipartite tree decompositions
by: Jaffke, Lars, et al.
Published: (2023)

Steiner Tree Parameterized by Multiway Cut and Even Less
by: Jansen, Bart M. P., et al.
Published: (2024)

An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets
by: Mundhra, S.
Published: (2025)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

Minimum-cost paths for electric cars
by: Dorfman, Dani, et al.
Published: (2024)

Exploration of $k$-edge-deficient temporal graphs in linear time
by: Lahtin, Ivan, et al.
Published: (2026)

Searching in trees with monotonic query times
by: Dereniowski, Dariusz, et al.
Published: (2024)

Finding irrelevant vertices in linear time on bounded-genus graphs
by: Golovach, Petr A., et al.
Published: (2019)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
by: Golovach, Petr A., et al.
Published: (2022)

Finding Diverse Minimum s-t Cuts
by: de Berg, Mark, et al.
Published: (2023)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)