Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Perfect code is W[1]-complete
Autore:
Cesati, M;
Indirizzi:
Univ Roma Tor Vergata, Dept Comp Sci Syst & Ind Engn, I-00133 Rome, Italy Univ Roma Tor Vergata Rome Italy I-00133 & Ind Engn, I-00133 Rome, Italy
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 3, volume: 81, anno: 2002,
pagine: 163 - 168
SICI:
0020-0190(20020214)81:3<163:PCIW>2.0.ZU;2-5
Fonte:
ISI
Lingua:
ENG
Soggetto:
FIXED-PARAMETER TRACTABILITY; COMPLETENESS; COMPUTATION; COMPLEXITY;
Keywords:
Computational Complexity; parameterized computational complexity; Perfect Code; weighted exact conjunctive normal form; satisfiability; W[1]-completeness;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
9
Recensione:
Indirizzi per estratti:
Indirizzo: Cesati, M Univ Roma Tor Vergata, Dept Comp Sci Syst & Ind Engn, Via Tor Vergata 110,I-00133 Rome, Italy Univ Roma Tor Vergata Via Tor Vergata 110 Rome Italy I-00133 ly
Citazione:
M. Cesati, "Perfect code is W[1]-complete", INF PROCESS, 81(3), 2002, pp. 163-168

Abstract

We show that the parameterized problem PERFECT CODE belongs to W[1]. This result closes an old open question, because it was often conjectured that PERFECT CODE could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership of the parameterized problem WEIGHTED EXACT CNF SATISFIABILITY. (C) 2002 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 19/01/20 alle ore 09:34:26