Improved approximations for weighted and unweighted graph problems

DOI10.1007/S00224-004-1162-6MaRDI QIDQ2581009zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Theoretical Computer Science
• scientific article; zbMATH DE number 1405687
• A note on the approximation of a minimum-weight maximal independent set
• Graph-Theoretic Concepts in Computer Science

Cited in

(9)

• Approximation algorithms for the weighted independent set problem in sparse graphs
• A note on the approximation of a minimum-weight maximal independent set
• On weighted vs unweighted versions of combinatorial optimization problems
• A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs
• On-line models and algorithms for max independent set
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Inductive graph invariants and approximation algorithms
• Algorithms and Computation
• Approximation of min coloring by moderately exponential algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581009)