LP-oriented upper bounds for the weighted stability number of a graph

DOI10.1007/S10559-009-9070-ZMaRDI QIDQ1040359zbMATH OpenOpenAlexFDO

Authors J. Blot

Publication date 24 November 2009

Published in Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10559-009-9070-z

zbMATH Keywords

\(p\)-wheel\(t\)-perfect graph\(W_{p}\)-perfect graphLP-oriented upper boundpolyhedron of stable setsweighted stability number of a graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• Improving an upper bound on the stability number of a graph
• Approximation of the stability number of a graph via copositive programming
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Lower bounds on the stability number of graphs computed in terms of degrees
• An SDP-based approach for computing the stability number of a graph
• On the \(\rho \)-edge stability number of graphs
• Stabilizing weighted graphs
• Stabilizing weighted graphs
• A nontrivial upper bound on the largest Laplacian eigenvalue of weighted graphs
• An upper bound on the spectral radius of weighted graphs

Cites work

• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 1041084 (Why is no real title available?)
• Nondifferentiable optimization and polynomial problems
• Problems of discrete optimization: challenges and main approaches to solve them
• Shortest paths algorithms: Theory and experimental evaluation
• Wheel inequalities for stable set polytopes

Cited in

(6)

• Lower bounds on the stability number of graphs computed in terms of degrees
• A note on the stability number of an orthogonality graph
• scientific article; zbMATH DE number 434686 (Why is no real title available?)
• scientific article; zbMATH DE number 3882469 (Why is no real title available?)
• Improving an upper bound on the stability number of a graph
• A quadratic programming approach to the determination of an upper bound on the weighted stability number

Describes a project that uses

Uses Software

• SoPlex
• DIMACS
• SCIP

This page was built for publication: LP-oriented upper bounds for the weighted stability number of a graph

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