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

DOI10.1023/A:1009755815678zbMATH Open0889.90152MaRDI QIDQ1369747FDOQ1369747

Authors: Gang Yu, Olivier Goldschmidt 

Publication date: 17 December 1997

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

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

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)

Cited In (6)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the solution bound of two-sided scaffold filling
• On locally optimal independent sets and vertex covers
• Packing triangles in low degree graphs and indifference graphs
• A 1.4-Approximation Algorithm for Two-Sided Scaffold Filling

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)