Buchumschlag

Balanced connected partitions of edge-weighted graphs: Hardness and solving methods

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Davari, Morteza, Moura, Phablo F. S., Yaman, Hande
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Discrete Mathematics 90C11, 68Q25
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Polyhedral approach to weighted connected matchings in general graphs
von: Samer, Phillippe, et al.
Veröffentlicht: (2023)

Covering and packing mixed-integer linear programs with a fixed number of constraints: Approximation and convex hull
von: Grobben, Kobe, et al.
Veröffentlicht: (2025)

Sublinear-Time Computation in the Presence of Online Erasures
von: Kalemaj, Iden, et al.
Veröffentlicht: (2021)

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases
von: Meusel, Julia, et al.
Veröffentlicht: (2025)

Coloring Hardness on Low Twin-Width Graphs
von: Bonnet, Édouard
Veröffentlicht: (2025)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
von: Laekhanukit, Bundit
Veröffentlicht: (2024)

Optimal Discretization is Fixed-parameter Tractable
von: Kratsch, Stefan, et al.
Veröffentlicht: (2020)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
von: Hougardy, Stefan, et al.
Veröffentlicht: (2025)

Answering Related Questions
von: Bonnet, Édouard
Veröffentlicht: (2025)

Reconfiguring homomorphisms to reflexive graphs via a simple reduction
von: Mühlenthaler, Moritz, et al.
Veröffentlicht: (2024)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
von: Feldman, Moran, et al.
Veröffentlicht: (2026)

A scalable clustering algorithm to approximate graph cuts
von: Suchan, Leo, et al.
Veröffentlicht: (2023)

An Algorithm to Recover Shredded Random Matrices
von: Atamanchuk, Caelan, et al.
Veröffentlicht: (2023)

Compact formulations and valid inequalities for parallel machine scheduling with conflicts
von: Moura, Phablo F. S., et al.
Veröffentlicht: (2023)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
von: Heimann, Sophia, et al.
Veröffentlicht: (2025)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
von: Heimann, Sophia, et al.
Veröffentlicht: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
von: Hougardy, Stefan, et al.
Veröffentlicht: (2024)

Interval Graphs are Reconstructible
von: Heinrich, Irene, et al.
Veröffentlicht: (2025)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
von: Foucaud, Florent, et al.
Veröffentlicht: (2026)

A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
von: Sun, Hao
Veröffentlicht: (2023)

Optimal Hardness of Online Algorithms for Large Independent Sets
von: Gamarnik, David, et al.
Veröffentlicht: (2025)

Generation of weighted trees, block trees and block graphs
von: Ekim, Tınaz, et al.
Veröffentlicht: (2024)

On weighted graph separation problems and flow-augmentation
von: Kim, Eun Jung, et al.
Veröffentlicht: (2022)

Supermodular Maximization with Cardinality Constraints
von: Chen, Xujin, et al.
Veröffentlicht: (2025)

Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole
von: Haxell, Penny, et al.
Veröffentlicht: (2022)

A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
von: Ammann, Sabrina C. L., et al.
Veröffentlicht: (2024)

Continuous optimization methods for the graph isomorphism problem
von: Klus, Stefan, et al.
Veröffentlicht: (2023)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
von: Liu, Bowen
Veröffentlicht: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2025)

A new width parameter of graphs based on edge cuts: $α$-edge-crossing width
von: Chang, Yeonsu, et al.
Veröffentlicht: (2023)

Designing sparse temporal graphs satisfying connectivity requirements
von: Bellitto, Thomas, et al.
Veröffentlicht: (2026)

The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
von: Goerigk, Marc, et al.
Veröffentlicht: (2026)

Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
von: Antony, Dhanyamol, et al.
Veröffentlicht: (2023)

APTAS for bin packing with general cost structures
von: Jaykrishnan, G., et al.
Veröffentlicht: (2024)

An Algorithm to Find Sums of Powers of Consecutive Primes
von: O'Sullivan, Cathal, et al.
Veröffentlicht: (2022)

Mim-Width is paraNP-complete
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
von: Bonnet, Édouard
Veröffentlicht: (2024)

Online Graph Balancing and the Power of Two Choices
von: Bansal, Nikhil, et al.
Veröffentlicht: (2026)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
von: Madathil, Jayakrishnan, et al.
Veröffentlicht: (2024)