Local approximations for maximum partial subgraph problem.

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

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

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 algorithms; APX-complete; problem; Local search; Hereditary property; Maximum subgraph; Minimum vertex deletion problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C85: Graph algorithms (graph-theoretic aspects)

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