Result: El problema de l’ordenació no linial òptima és np-complet
Title:
El problema de l’ordenació no linial òptima és np-complet
Authors:
Source:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Qüestiió: quaderns d'estadística i investigació operativa; 1978: Vol.: 2 Núm.: 4; p. 257-260
Universitat Politècnica de Catalunya (UPC)
Qüestiió: quaderns d'estadística i investigació operativa; 1978: Vol.: 2 Núm.: 4; p. 257-260
Publisher Information:
Universitat Politècnica de Barcelona. Centre de Càlcul, 1978.
Publication Year:
1978
Subject Terms:
Classificació AMS::90 Operations research, mathematical programming::90C Mathematical programming, Programació (Matemàtica), Mathematical programming, 90 Operations research, mathematical programming::90C Mathematical programming [Classificació AMS], Classificació AMS::90 Operations research, mathematical programming::90C Mathematical programming
Document Type:
Academic journal
Article
File Description:
application/pdf; p. 257-260
Language:
Catalan; Valencian
Access URL:
Rights:
CC BY NC ND
Accession Number:
edsair.dedup.wf.002..8d13a40c14f1b9f0961e2a8dda1728fe
Database:
OpenAIRE
Further Information
This article describes the reducibility of Simple Max Cut to Optimal Non Linear Arrangement, so to make the Optimal Non Linear Arrangement one element of the class NP-Complete. The reduction is simylar, i.e. of difficult solution in polynomial time, to the one by Garey and Johnson for the linear case.
L'article descriu la reducció del Problema de Tall màxim Simple al Problema de l'Ordenació no Lineal Òptima, la qual cosa implica la pertinença d'aquest últim a la classe NP-Complet.