Approximation Algorithms for Some Graph Partitioning Problems

DOI10.7155/jgaa.00021zbMath0969.05057OpenAlexW2135006981MaRDI QIDQ4511245

George He, Ji Ping 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

zbMATH Keywords

graph partitioningcliquesapproximation algorithmsmatching algorithmsexperimental testing

Mathematics Subject Classification ID

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

Related Items (7)

Colourful components in \(k\)-caterpillars and planar graphs ⋮ Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem ⋮ Generalized \(k\)-multiway cut problems ⋮ Algorithmic and hardness results for the colorful components problems ⋮ OMG! Orthologs in Multiple Genomes – Competing Graph-Theoretical Formulations ⋮ Finding a Small Number of Colourful Components ⋮ Scalable Algorithms for Multiple Network Alignment

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