WFRF:(Kann Viggo)
Sökning: WFRF:(Kann Viggo) > Some APX-completene...
Some APX-completeness results for cubic graphs
- Alimonti, P. (författare)
-
- Kann, Viggo (författare)
- KTH,Numerisk analys och datalogi, NADA
- (creator_code:org_t)
- 2000
- 2000
- Engelska.
- Ingår i: Theoretical Computer Science. - 0304-3975 .- 1879-2294. ; 237:2-Jan, s. 123-134
- Tidskriftsartikel (refereegranskat)
Abstract
Ämnesord
Stäng
- Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.
Nyckelord
- computational complexity
- NP-hard optimization problems
- approximation
- APX-completeness
- cubic graphs
- approximation classes
- complexity
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
- Theoretical Computer Science (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
Hitta mer i SwePub
- Av författaren/redakt...
- Alimonti, P.
- Kann, Viggo
- Artiklar i publikationen
- Theoretical Comp ...
- Av lärosätet
- Kungliga Tekniska Högskolan
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
