×

An algorithm for partitioning the nodes of a graph. (English) Zbl 0505.05050


MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity
05C35 Extremal problems in graph theory
Full Text: DOI

References:

[1] Friedman, ArthurD.; Menon, PremachandranR., Theory & design of switching circuits, (1975)
[2] Russo, R. L.; Oden, P. H.; Wolff Sr., P. K., A heuristic procedure for the partitioning and mapping of computer logic blocks to modules, IEEE Trans. Comput., C-20, 1455, (1971)
[3] Efficient partitioning of componentsShare/ACM/IEEE Design Automation WorkshopWashington, DC1968July
[4] A study of user program optimization in a paging systemACM Symposium on Operating System PrinciplesGatlinburg, TN1967October
[5] Denning, P. J., Virtual memory, Comput. Surveys, 2, 153, (1970) · Zbl 0198.50702 · doi:10.1145/356571.356573
[6] Ph.D. ThesisSome graph partitioning problems related to program segmentationPrinceton Univ.Princeton, NJ1969
[7] Kernighan, B. W.; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell Systems Tech. J., 49, 291, (1970) · Zbl 0333.05001
[8] Hoffman, A. J.; Wielandt, H. W., The variation of the spectrum of a normal matrix, Duke Math. J., 20, 37, (1953) · Zbl 0051.00903
[9] Hadley, G., Linear programming, (1962) · Zbl 0102.36304
[10] A block Lanczos algorithm for computing the q algebraically largest eigenvalues and a corresponding eigenspace of large, sparse, real symmetric matricesProc. of the 1974 IEEE Conference on Decision and ControlPhoenix, AZ1974505509November
[11] Donath, W. E.; Hoffman, A. J., Lower bounds for the partitioning of graphs, IBM J. Res. Develop., 17, 420, (1973) · Zbl 0259.05112
[12] Lawler, EugeneL., Combinatorial optimization: networks and matroids, (1976) · Zbl 0413.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.