Improved approximations for weighted and unweighted graph problems

DOI10.1007/s00224-004-1162-6zbMath1085.68105OpenAlexW1972228828MaRDI QIDQ2581009

Marc Demange, Vangelis Th. Paschos

Publication date: 10 January 2006

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-004-1162-6

zbMATH Keywords

weighted hereditary induced-subgraph maximization problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (4)

Approximation of min coloring by moderately exponential algorithms ⋮ Approximation algorithms for the weighted independent set problem in sparse graphs ⋮ On-line models and algorithms for max independent set ⋮ A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs

This page was built for publication: Improved approximations for weighted and unweighted graph problems