Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs

DOI10.1137/0220012MaRDI QIDQ3210198zbMATHOpenAlexFDO

Authors E. Balas, Jue Xue

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

zbMATH Keywords

graph coloringtriangulated graphsvertex packingmaximum clique finding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Addendum: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• Optimizing weakly triangulated graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• scientific article; zbMATH DE number 3893237

Cited in

(33)

• A network-flow-based lower bound for the minimum weighted integer coloring problem
• Cliques and clustering: A combinatorial approach
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• An algorithm for finding a maximum clique in a graph
• Solving the maximum clique problem using a tabu search approach
• Maximum weight perfect matching problem with additional disjunctive conflict constraints
• A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• Solving the minimum-weighted coloring problem
• Addendum: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• Constructing a course schedule by solving a series of assignment type problems
• On risk-averse maximum weighted subgraph problems
• On column generation formulations for the RWA problem
• Test case generators and computational results for the maximum clique problem
• Dual inequalities for stabilized column generation revisited
• Packing \(r\)-cliques in weighted chordal graphs
• A fast algorithm for the maximum weight clique problem
• A parallel algorithm for minimum weighted colouring of triangulated graphs
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• Safe lower bounds for graph coloring
• Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
• Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
• The maximum clique problem
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• Optimizing weakly triangulated graphs
• New lower bounds on the weighted chromatic number of a graph
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• A new upper bound for the maximum weight clique problem
• Solving the anti-covering location problem using Lagrangian relaxation
• Scheduling independent tasks with multiple modes
• Maximum-weight stable sets and safe lower bounds for graph coloring
• scientific article; zbMATH DE number 4031729 (Why is no real title available?)

This page was built for publication: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs

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