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 (34)

• 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
• 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
• Parameterized approximation algorithms for some location problems in graphs
• Title not available (Why is that?)
• On the clique partitioning problem in weighted interval graphs
• Comparison of algorithms in graph partitioning
• Some graph partitioning problems
• A linear time algorithm for graph partition problems
• Algorithmic and hardness results for the colorful components problems
• 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
• Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem
• 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?)
• Scalable Algorithms for Multiple Network Alignment
• 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?)
• Finding a Small Number of Colourful Components

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)