Independent sets of maximum weight in (\(p,q\))-colorable graphs.

DOI10.1016/S0012-365X(02)00877-4zbMath1034.05020OpenAlexW2096226903MaRDI QIDQ1874371

Vadim V. Lozin, Vladimir E. Alekseev

Publication date: 25 May 2003

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(02)00877-4

zbMATH Keywords

independent setweighted graphpolynomial algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

A dichotomy for minimum cost graph homomorphisms ⋮ Classes of perfect graphs ⋮ Independent sets in graphs ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of generalized clique packing
• Matching theory
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• A nice class for the vertex packing problem
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH

This page was built for publication: Independent sets of maximum weight in (\(p,q\))-colorable graphs.