Covering problems (original) (raw)
Els problemes de recobriment són normalment problemes de minimització i programació lineal, els dels quals s'anomenen . Els exemples més prominents de problemes de recobriment són el .
| Property | Value |
|---|---|
| dbo:abstract | Els problemes de recobriment són normalment problemes de minimització i programació lineal, els dels quals s'anomenen . Els exemples més prominents de problemes de recobriment són el . (ca) In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems and usually integer linear programs, whose dual problems are called packing problems. The most prominent examples of covering problems are the set cover problem, which is equivalent to the hitting set problem, and its special cases, the vertex cover problem and the edge cover problem. (en) En combinatoria y ciencias de la computación, los problemas de cobertura son problemas computacionales que preguntan si una determinada estructura combinatoria 'cubre' a otra, o qué tan grande debe ser la estructura para hacer eso. Los problemas de cobertura son problemas de minimización y, por lo general, programas lineales, cuyos problemas duales se denominan problemas de empaque. Los ejemplos más destacados de problemas de cobertura son el problema de cobertura de conjuntos, que es equivalente al problema de acierto de conjuntos, y sus casos especiales, el problema de cobertura de vértices y el problema de cobertura de bordes. (es) |
| dbo:wikiPageID | 1045640 (xsd:integer) |
| dbo:wikiPageLength | 6535 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116006401 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Arboricity dbr:Vertex_cover_problem dbr:Independent_set_(graph_theory) dbr:Matrix_(mathematics) dbr:Optimization_(mathematics) dbr:Combinatorics dbr:Computational_geometry dbr:Computer_science dbr:Petri_net dbr:Linear_programming dbr:Packing_problems dbr:Graph_theory dbr:Hitting_set dbr:Mathematical_proof dbr:Interval_(mathematics) dbc:Covering_problems dbr:Set_cover_problem dbr:NP-hardness dbr:Real_line dbr:Integer_linear_program dbr:Integer_linear_programs dbr:Subset dbr:Dual_problem dbr:Linear_SAT dbr:Fixed-parameter_algorithm dbr:Edge_cover_problem |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Reflist dbt:Short_description dbt:Covering-Packing_Problem_Pairs |
| dct:subject | dbc:Covering_problems |
| gold:hypernym | dbr:Problems |
| rdf:type | yago:WikicatComputationalProblems yago:WikicatMathematicalProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Disease yago:State100024720 |
| rdfs:comment | Els problemes de recobriment són normalment problemes de minimització i programació lineal, els dels quals s'anomenen . Els exemples més prominents de problemes de recobriment són el . (ca) In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems and usually integer linear programs, whose dual problems are called packing problems. The most prominent examples of covering problems are the set cover problem, which is equivalent to the hitting set problem, and its special cases, the vertex cover problem and the edge cover problem. (en) En combinatoria y ciencias de la computación, los problemas de cobertura son problemas computacionales que preguntan si una determinada estructura combinatoria 'cubre' a otra, o qué tan grande debe ser la estructura para hacer eso. Los problemas de cobertura son problemas de minimización y, por lo general, programas lineales, cuyos problemas duales se denominan problemas de empaque. (es) |
| rdfs:label | Covering problems (en) Problema del recobriment (ca) Problema de cobertura (combinatoria) (es) |
| owl:sameAs | freebase:Covering problems yago-res:Covering problems wikidata:Covering problems dbpedia-ca:Covering problems dbpedia-es:Covering problems https://global.dbpedia.org/id/4iNRY |
| prov:wasDerivedFrom | wikipedia-en:Covering_problems?oldid=1116006401&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Covering_problems |
| is dbo:wikiPageRedirects of | dbr:Covering_Problem dbr:Covering_problem dbr:Rainbow_covering |
| is dbo:wikiPageWikiLink of | dbr:Vertex_cover dbr:Dorit_S._Hochbaum dbr:Erdős_on_Graphs dbr:Covering_Problem dbr:Covering_problem dbr:Art_Gallery_Theorems_and_Algorithms dbr:Polygon_covering dbr:Włodzimierz_Kuperberg dbr:Multiplicative_weight_update_method dbr:Rainbow_covering |
| is foaf:primaryTopic of | wikipedia-en:Covering_problems |