An algorithm for the maximum internally stable set in a weighted graph

DOI10.1080/00207168308803357zbMath0502.68013OpenAlexW2048347878MaRDI QIDQ3968462

Emmanuel Loukakis, Constantine Tsouros

Publication date: 1983

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

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

zbMATH Keywords

NP-hardweighted undirected graphrecursive backtracking algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

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
• Unnamed Item
• On maximal independent sets of vertices in claw-free graphs
• A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
• Some simplified NP-complete graph problems
• Anti-blocking polyhedra
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Finding maximum cliques in circle graphs
• Determining the number of internal stability of a graph
• Finding a Maximum Independent Set
• Determining the Stability Number of a Graph
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: An algorithm for the maximum internally stable set in a weighted graph