Balanced connected partitions of graphs: approximation, parameterization and lower bounds

DOI10.1007/S10878-023-01058-XMaRDI QIDQ6166191zbMATH OpenFDO

Authors Phablo F. S. Moura, Matheus Jun Ota, Yoshiko Wakabayashi

Publication date 2 August 2023

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-023-01058-X

zbMATH Keywords

approximation algorithmsfixed parameter tractablebalanced connected partitionfractional partitioncomplexity lower bound

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Approximation and inaproximability results on balanced connected partitions of graphs
• Approximation algorithms for maximally balanced connected graph partition
• Approximation algorithms for maximally balanced connected graph partition
• Approximation algorithms for the maximally balanced connected graph tripartition problem
• Max-min weight balanced connected partition

Cites work

• scientific article; zbMATH DE number 432817 (Why is no real title available?)
• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• scientific article; zbMATH DE number 7740881 (Why is no real title available?)
• A Shifting Algorithm for Min-Max Tree Partitioning
• A homology theory for spanning tress of a graph
• A linear algorithm for bipartition of biconnected graphs
• A linear-time algorithm for four-partitioning four-connected planar graphs
• A polynomial-time algorithm for max-min partitioning of ladders
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Approximation algorithms for maximally balanced connected graph partition
• Approximation algorithms for the maximally balanced connected graph tripartition problem
• Approximation and inaproximability results on balanced connected partitions of graphs
• Approximation and parameterized algorithms for balanced connected partition problems
• Clustering on trees
• 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
• Graph Layout Problems Parameterized by Vertex Cover
• Integer Programming with a Fixed Number of Variables
• Max-Min Tree Partitioning
• Max-min partitioning of grid graphs into connected components
• Minkowski's Convex Body Theorem and Integer Programming
• Most uniform path partitioning and its use in image processing
• On the complexity of k-SAT
• On the complexity of partitioning graphs into connected subgraphs
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Shifting algorithms for tree partitioning with general weighting functions
• What makes equitable connected partition easy
• Which problems have strongly exponential complexity?

Cited in

(7)

• LOCALLY-BALANCED k-PARTITIONS OF GRAPHS
• Complexity and inapproximability results for balanced connected subgraph problem
• Approximation algorithm for the balanced 2-connected k-partition problem
• On the parameterized complexity of computing balanced partitions in graphs
• Approximation algorithms for maximally balanced connected graph partition
• Approximation and parameterized algorithms for balanced connected partition problems
• scientific article; zbMATH DE number 6311292 (Why is no real title available?)

This page was built for publication: Balanced connected partitions of graphs: approximation, parameterization and lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166191)