Local optimality and its application on independent sets for k-claw free graphs

DOI10.1023/A:1009755815678MaRDI QIDQ1369747zbMATH OpenFDO

Authors Gang Yu, Olivier Goldschmidt

Publication date 17 December 1997

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmspolynomial time\(k\)-claw free graphslocally optimal independent sets

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On locally optimal independent sets and vertex covers
• A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
• Counting independent sets in claw-free graphs

Cited in

(6)

• On locally optimal independent sets and vertex covers
• On the solution bound of two-sided scaffold filling
• scientific article; zbMATH DE number 1617260 (Why is no real title available?)
• A 1.4-Approximation Algorithm for Two-Sided Scaffold Filling
• scientific article; zbMATH DE number 2079339 (Why is no real title available?)
• Packing triangles in low degree graphs and indifference graphs

This page was built for publication: Local optimality and its application on independent sets for \(k\)-claw free graphs

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