Balanced connected partitions of graphs: approximation, parameterization and lower bounds
From MaRDI portal
Publication:6166191
DOI10.1007/s10878-023-01058-xMaRDI QIDQ6166191
Phablo F. S. Moura, Yoshiko Wakabayashi, Matheus Jun Ota
Publication date: 2 August 2023
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
approximation algorithmsfixed parameter tractablebalanced connected partitionfractional partitioncomplexity lower bound
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for four-partitioning four-connected planar graphs
- Approximating the Maximally Balanced Connected Partition Problem in graphs
- A linear algorithm for bipartition of biconnected graphs
- On the complexity of partitioning graphs into connected subgraphs
- An application of simultaneous diophantine approximation in combinatorial optimization
- Clustering on trees
- Which problems have strongly exponential complexity?
- Most uniform path partitioning and its use in image processing
- Partitioning a graph into balanced connected classes: formulations, separation and experiments
- Approximation algorithms for the maximally balanced connected graph tripartition problem
- Cut and flow formulations for the balanced connected \(k\)-partition problem
- FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS
- Integer Programming with a Fixed Number of Variables
- Graph Layout Problems Parameterized by Vertex Cover
- What Makes Equitable Connected Partition Easy
- Shifting algorithms for tree partitioning with general weighting functions
- Minkowski's Convex Body Theorem and Integer Programming
- Max-Min Tree Partitioning
- A Shifting Algorithm for Min-Max Tree Partitioning
- A homology theory for spanning tress of a graph
- Max-min partitioning of grid graphs into connected components
- Approximation algorithms for maximally balanced connected graph partition
- On the complexity of \(k\)-SAT
- A polynomial-time algorithm for max-min partitioning of ladders
- Approximation and parameterized algorithms for balanced connected partition problems
This page was built for publication: Balanced connected partitions of graphs: approximation, parameterization and lower bounds