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

DOI10.1137/0220012zbMATH Open0722.68086OpenAlexW4253314095MaRDI QIDQ3210198FDOQ3210198

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)

Cited In (29)

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

   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 👍 👎
• Title not available (Why is that?) 👍 👎

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)