Fast approximation algorithms on maxcut, k-coloring, and k-color ordering for VLSI applications

DOI10.1109/12.736440zbMath1392.68443OpenAlexW2151997344MaRDI QIDQ4571486

Salil Raje, Majid Sarrafzadeh, Jun Dong Cho

Publication date: 9 July 2018

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/12.736440

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Mathematical problems of computer architecture (68M07) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

An effective iterated tabu search for the maximum bisection problem, Conjugate conflict continuation graphs for multi-layer constrained via minimization, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, A multiple search operator heuristic for the max-k-cut problem