Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
From MaRDI portal
Publication:3210198
DOI10.1137/0220012zbMath0722.68086OpenAlexW4253314095MaRDI QIDQ3210198
Publication date: 1991
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0220012
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Solving the maximum clique problem using a tabu search approach ⋮ Efficient algorithms for minimum weighted colouring of some classes of perfect graphs ⋮ Scheduling independent tasks with multiple modes ⋮ Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring ⋮ Solving the anti-covering location problem using Lagrangian relaxation ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ On risk-averse maximum weighted subgraph problems ⋮ Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ Safe Lower Bounds for Graph Coloring ⋮ A new upper bound for the maximum weight clique problem ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ Dual Inequalities for Stabilized Column Generation Revisited ⋮ Cliques and clustering: A combinatorial approach ⋮ An algorithm for finding a maximum clique in a graph ⋮ On column generation formulations for the RWA problem ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Constructing a course schedule by solving a series of assignment type problems ⋮ A network-flow-based lower bound for the minimum weighted integer coloring problem ⋮ Test case generators and computational results for the maximum clique problem ⋮ A fast algorithm for the maximum weight clique problem ⋮ The maximum clique problem
