A 0.3622-approximation algorithm for the maximum k-edge-colored clustering problem

DOI10.1007/978-3-030-58657-7_1MaRDI QIDQ4965094zbMATH OpenOpenAlexFDO

Authors

Publication date 25 February 2021

Published in Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-58657-7_1

zbMATH Keywords

approximation algorithmclustering problemedge-colored graphlinear relaxationworst-case analysis

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Approximability and inapproximability for maximum \(k\)-edge-colored clustering problem
• Improved approximations for the max \(k\)-colored clustering problem
• Clustering on \(k\)-edge-colored graphs
• Clustering on k-Edge-Colored Graphs
• Approximating the maximum 2- and 3-edge-colorable subgraph problems

Cites work

• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Approximability and inapproximability for maximum \(k\)-edge-colored clustering problem
• Clustering on \(k\)-edge-colored graphs
• Clustering on k-Edge-Colored Graphs
• Improved approximations for the max \(k\)-colored clustering problem
• Information-sharing in social networks
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey

Cited in

(7)

• Clustering as a dual problem to colouring
• Approximability and inapproximability for maximum \(k\)-edge-colored clustering problem
• Clustering on k-Edge-Colored Graphs
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Clustering on \(k\)-edge-colored graphs
• Improved approximations for the max \(k\)-colored clustering problem
• Clique clustering yields a PTAS for max-coloring interval graphs

This page was built for publication: A 0.3622-approximation algorithm for the maximum \(k\)-edge-colored clustering problem

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