Result: Computing a K-independent set of maximal weight on a partially ordered set: a research case history

Title:
Computing a K-independent set of maximal weight on a partially ordered set: a research case history
Authors:
Berenguer, Xavier
Source:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Qüestiió: quaderns d'estadística i investigació operativa; 1981: Vol.: 5 Núm.: 1; p. 25-29
Publisher Information:
Universitat Politècnica de Barcelona. Centre de Càlcul, 1981.
Publication Year:
1981
Subject Terms:
Classificació AMS::90 Operations research, mathematical programming::90B Operations research and management science, 90 Operations research, mathematical programming::90B Operations research and management science [Classificació AMS], Operations research, Investigació operativa, Classificació AMS::90 Operations research, mathematical programming::90B Operations research and management science
Document Type:
Academic journal Article
File Description:
application/pdf; p. 25-29
Language:
English
Access URL:
http://hdl.handle.net/2099/4406
https://hdl.handle.net/2099/4406
http://www.raco.cat/index.php/Questiio/article/view/26379
Rights:
CC BY NC ND
Accession Number:
edsair.dedup.wf.002..f83e409e85c702238d863cbc4b7bd82c
Database:
OpenAIRE

Further Information

This is a tutorial paper presenting the research carried out on the Sperner-Erdös problem, that is the problem of computing a Maximal Weighted K-Independent Set on a Partially Ordered set. Results are shown in the same order as the research was made: analysis and solution to the Sperner [sub]problem (K=1) and generalisation of this result yielding a polynomial solution to the Sperner-Erdös problem.