A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound

✍ Scribed by Svatopluk Poljak; Daniel Turzík

• Publisher: Elsevier Science
• Year: 1986
• Tongue: English
• Weight: 340 KB
• Volume: 58
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(86)90192-5

✦ Synopsis

We introduce a notion of ).-extendible property of graphs and prove: If P is a ).-extendible property (0<).<1), then for a connected graph G = (V, E) and an objective function c: E---*R + one can construct a spanning subgraph H= (V, F) which has the property P and satisfies c(F) = ~. c(E) + ½