Local approximations for maximum partial subgraph problem.

DOI10.1016/j.orl.2003.08.004zbMath1046.90099OpenAlexW2042951465MaRDI QIDQ1426723

Sophie Toulouse, Jérôme Monnot, Vangelis Th. Paschos

Publication date: 15 March 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2099

zbMATH Keywords

Approximation algorithmsAPX-completeproblemLocal searchHereditary propertyMaximum subgraphMinimum vertex deletion problem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• Optimization, approximation, and complexity classes
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Local search for the minimum label spanning tree problem with bounded color classes.
• Approximation properties of NP minimization classes
• z-Approximations
• Edge-Deletion Problems
• On Syntactic versus Computational Views of Approximability
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• The approximation of maximum subgraph problems
• On the complexity of the Maximum Subgraph Problem

This page was built for publication: Local approximations for maximum partial subgraph problem.