On locally optimal independent sets and vertex covers

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1520-6750(199608)43:5<737::AID-NAV9>3.0.CO;2-6" /><737::AID-NAV9>3.0.CO;2-6 10.1002/(SICI)1520-6750(199608)43:5<737::AID-NAV9>3.0.CO;2-6zbMath0860.05063OpenAlexW2011134696MaRDI QIDQ5687646

Gang Yu, Olivier Goldschmidt

Publication date: 21 April 1997

Full work available at URL: https://doi.org/10.1002/(sici)1520-6750(199608)43:5<737::aid-nav9>3.0.co;2-6

zbMATH Keywords

approximation algorithmlocal searchindependent setdisk graphsvertex coverclaw-free graphsline graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (1)

Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs

This page was built for publication: On locally optimal independent sets and vertex covers