The travelling preacher, projection, and a lower bound for the stability number of a graph

DOI10.1016/J.DISOPT.2007.08.005zbMATH Open1151.90056OpenAlexW2090424186MaRDI QIDQ951102FDOQ951102

Kathie Cameron, Jack Edmonds

Publication date: 29 October 2008

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

Full work available at URL: https://doi.org/10.1016/j.disopt.2007.08.005

Recommendations

• Lower bounds on the stability number of graphs computed in terms of degrees
• A combinatorial column generation algorithm for the maximum stable set problem
• Applications of the Inverse Theta Number in Stable Set Problems
• Minimum degree algorithms for stability number
• Polynomially solvable cases for the maximum stable set problem

zbMATH Keywords

network flowtotal dual integralitystable setcirculationGallai's conjectureprojection of a polyhedrontravelling salesman cost allocation game

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Title not available (Why is that?)
• Minimum cost spanning tree games
• Geometric algorithms and combinatorial optimization.
• On approximately fair cost allocation in Euclidean TSP games
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Minmax relations for cyclically ordered digraphs
• Combinatorial optimization. Theory and algorithms.
• Coflow polyhedra

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: The travelling preacher, projection, and a lower bound for the stability number of a graph

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