Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

Author： Hemaspaandra Edith   Rothe Jörg   Spakowski Holger  

Publisher： Edp Sciences

E-ISSN： 1290-385x|40|1|75-91

ISSN： 0988-3754

Source： RAIRO - Theoretical Informatics and Applications, Vol.40, Iss.1, 2010-03, pp. : 75-91

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Related content

The partial inverse minimum cut problem with L1-norm is strongly NP-hard

By Gassner Elisabeth  

RAIRO - Operations Research, Vol. 44, Iss. 3, 2010-10 ,pp. : 241-249

Edp Sciences

Access to resources Recommend Favorite

On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem

By Mishra Sounaka   Sikdar Kripasindhu  

RAIRO - Theoretical Informatics and Applications, Vol. 35, Iss. 3, 2010-03 ,pp. : 287-309

Edp Sciences

Access to resources Recommend Favorite

Minimum convex-cost tension problems on series-parallel graphs

By Bachelet Bruno   Mahey Philippe  

RAIRO - Operations Research, Vol. 37, Iss. 4, 2010-03 ,pp. : 221-234

Edp Sciences

Access to resources Recommend Favorite

Optimum orientation of parallel parametric speakers for simultaneous guide audio with minimum cross-talk

By Kondo Kazuhiro  

INTER-NOISE and NOISE-CON Congress and Conference Proceedings, Vol. 2011, Iss. 5, 2011-07 ,pp. : 2858-2862

Institute of Noise Control Engineering

Access to resources Recommend Favorite

Start-Up Challenges in A Slow Economy: When Less than Design Minimum Rules

By Callahan Keli   Leveque Eric   Machado Jose Christiano  

Proceedings of the Water Environment Federation, Vol. 2011, Iss. 17, 2011-01 ,pp. : 551-565

Water Environment Federation

Access to resources Recommend Favorite