An algorithm for finding a maximum weighted independent set in an arbitrary graph

DOI10.1080/00207169108803967zbMath0723.68085OpenAlexW2088500299WikidataQ126245503 ScholiaQ126245503MaRDI QIDQ3210915

Nisha Desai, Panos M. Pardalos

Publication date: 1991

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169108803967

zbMATH Keywords

optimizationheuristicsbranch and bounddepth first searchmaximum weighted independent setnongreedy approach

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Solving the maximum clique problem using a tabu search approach, 0-1 Quadratic programming approach for optimum solutions of two scheduling problems, Branch-and-bound techniques for the maximum planar subgraph problem^∗, On a posterior evaluation of a simple greedy method for set packing, Genetic algorithmic approach to find the maximum weight independent set of a graph, A hybrid iterated local search heuristic for the maximum weight independent set problem, Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound, Algorithm for optimal winner determination in combinatorial auctions, A fast algorithm for the maximum weight clique problem, The maximum clique problem

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture
• Clique detection for nondirected graphs: Two new algorithms
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Finding a Maximum Clique in an Arbitrary Graph
• On the Maximum Weight Clique Problem
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Determining the number of internal stability of a graph
• A global optimization approach for solving the maximum clique problem
• Finding a Maximum Independent Set
• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithm 457: finding all cliques of an undirected graph
• A branch and bound algorithm for the maximum clique problem