Approximation Algorithms for Some Graph Partitioning Problems

DOI10.7155/JGAA.00021zbMATH Open0969.05057OpenAlexW2135006981MaRDI QIDQ4511245FDOQ4511245

Authors: George He, Jiping Liu, Cheng Zhao 

Publication date: 14 December 2000

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/228573

Recommendations

• A class of bounded approximation algorithms for graph partitioning
• One-Half Approximation Algorithms for the k-Partition Problem
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• Some graph partitioning problems
• scientific article; zbMATH DE number 3891429

zbMATH Keywords

approximation algorithmsgraph partitioningcliquesexperimental testingmatching algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (35)

• Title not available (Why is that?)
• Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach
• A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs
• Fundamentals of Computation Theory
• A class of bounded approximation algorithms for graph partitioning
• Scalable algorithms for multiple network alignment
• Title not available (Why is that?)
• Approximation algorithms for fragmenting a graph against a stochastically-located threat
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
• Approximation algorithms for array partitioning problems
• Generalized \(k\)-multiway cut problems
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
• Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
• Finding a small number of colourful components
• Title not available (Why is that?)
• On the clique partitioning problem in weighted interval graphs
• Approximation and hardness results for the maximum edges in transitive closure problem
• Comparison of algorithms in graph partitioning
• Some graph partitioning problems
• A linear time algorithm for graph partition problems
• On the approximability of the minimum weight \(t\)-partite clique problem
• Approximating element-weighted vertex deletion problems for the complete \(k\)-partite property
• Colourful components in \(k\)-caterpillars and planar graphs
• Approximation algorithms for the partial assignment problem
• Approximation algorithms for maximization problems arising in graph partitioning
• Title not available (Why is that?)
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem
• OMG! Orthologs in multiple genomes -- competing graph-theoretical formulations
• Title not available (Why is that?)
• Approximation algorithms for maximally balanced connected graph partition
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Title not available (Why is that?)
• On approximability of optimization problems related to red/blue-split graphs
• Title not available (Why is that?)

This page was built for publication: Approximation Algorithms for Some Graph Partitioning Problems

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