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)

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)