Finding good approximate vertex and edge partitions is NP-hard
References (10)
- et al.
Some simplified NP-complete graph problems
Theoret. Comput. Sci.
(1976) - et al.
Graph bisection algorithms with good average case behavior
Combinatorica
(1987) - et al.
Improving the performance of the Kernighan–Lin and simulated annealing graph bisection algorithms
Proc. 26th Design Automation Conf.
(1989) - et al.
Parallel algorithms for partitioning simple classes of graphs
Proc. 1990 Internat. Conf. on Parallel Processing
(1990) - et al.
Partitioning planar graphs
SIAM J. Comput.
(1992)
There are more references available in the full text version of this article.
Cited by (287)
Scalable timing-aware network design via lagrangian decomposition
2023, European Journal of Operational ResearchSemi-Supervised Graph Neural Networks for Graph Partitioning Problem
2023, Procedia Computer ScienceModified Coot bird optimization algorithm for solving community detection problem in social networks
2024, Neural Computing and ApplicationsBuffered Streaming Edge Partitioning
2024, arXivIdentifying Best Goalkeepers Problem is a NP-Hard?
2024, Smart Innovation, Systems and TechnologiesParallel Unconstrained Local Search for Partitioning Irregular Graphs
2024, Proceedings of the Workshop on Algorithm Engineering and Experiments
Copyright © 1992 Published by Elsevier B.V.