A class of bounded approximation algorithms for graph partitioning

DOI10.1002/NET.3230200205zbMATH Open0696.90074OpenAlexW2033954061MaRDI QIDQ3474493FDOQ3474493

Authors: Thomas A. Feo, Mallek Khellaf 

Publication date: 1990

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230200205

Recommendations

• Approximation Algorithms for Some Graph Partitioning Problems
• scientific article; zbMATH DE number 4011955
• One-Half Approximation Algorithms for the k-Partition Problem
• scientific article; zbMATH DE number 1538871
• A computational study of graph partitioning

zbMATH Keywords

heuristicsmatchingheuristicweighted graphGraph partitioningbounded approximation algorithmsequal-sized disjoint subsets

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• An Efficient Heuristic Procedure for Partitioning Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (35)

• Truthful Mechanisms for Matching and Clustering in an Ordinal World
• One-Half Approximation Algorithms for the k-Partition Problem
• Title not available (Why is that?)
• Approximation algorithms for maximum dispersion
• On using learning automata for fast graph partitioning
• A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs
• Title not available (Why is that?)
• The balanced maximally diverse grouping problem with attribute values
• The balanced maximally diverse grouping problem with integer attribute values
• An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes
• Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping
• Approximation algorithms for fragmenting a graph against a stochastically-located threat
• Solving balanced multi-weighted attribute set partitioning problem with variable neighborhood search
• Approximation Algorithms for Some Graph Partitioning Problems
• Title not available (Why is that?)
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
• Approximation algorithms for the metric maximum clustering problem with given cluster sizes.
• Approximating the maximum quadratic assignment problem
• Minimum transversals of maximum matchings as approximate solutions to the bisection problem
• Iterated maxima search for the maximally diverse grouping problem
• A black-box scatter search for optimization problems with integer variables
• NP-hardness of \(m\)-dimensional weighted matching problems
• Approximation algorithms for maximization problems arising in graph partitioning
• Title not available (Why is that?)
• Efficient neighborhood evaluation for the maximally diverse grouping problem
• A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem
• Title not available (Why is that?)
• Solution of large weighted equicut problems
• Tabu search for graph partitioning
• Generating irregular partitionable data structures
• A complementary column generation approach for the graph equipartition problem
• A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values
• Approximation algorithms for multi-dimensional assignment problems with decomposable costs
• Balanced tree partition problems with virtual nodes
• Balanced partitions of trees and applications

This page was built for publication: A class of bounded approximation algorithms for graph partitioning

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