| dbo:abstract
|
- In computer science, iterative compression is an algorithmic technique for the design of fixed-parameter tractable algorithms, in which one element (such as a vertex of a graph) is added to the problem in each step, and a small solution for the problem prior to the addition is used to help find a small solution to the problem after the step. The technique was invented by Reed, Smith and Vetta to show that the problem of odd cycle transversal was solvable in time O(3k kmn), for a graph with n vertices, m edges, and odd cycle transversal number k. Odd cycle transversal is the problem of finding the smallest set of vertices of a graph that include at least one vertex from every odd cycle; its parameterized complexity was a longstanding open question. This technique later proved very useful in showing fixed-parameter tractability results. It is now considered to be one of the fundamental techniques in the area of parameterized algorithmics. Iterative compression has been used successfully in many problems, for instance odd cycle transversal (see below) and edge bipartization, feedback vertex set, cluster vertex deletion and directed feedback vertex set. It has also been used successfully for exact exponential time algorithms for independent set. (en)
- Итеративное сжатие — это алгоритмическая техника разработки . В данной технике на каждом шаге в задачу добавляется один элемент (такой как вершина графа), а перед его добавлением находится небольшое решение задачи. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8751 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Итеративное сжатие — это алгоритмическая техника разработки . В данной технике на каждом шаге в задачу добавляется один элемент (такой как вершина графа), а перед его добавлением находится небольшое решение задачи. (ru)
- In computer science, iterative compression is an algorithmic technique for the design of fixed-parameter tractable algorithms, in which one element (such as a vertex of a graph) is added to the problem in each step, and a small solution for the problem prior to the addition is used to help find a small solution to the problem after the step. (en)
|
| rdfs:label
|
- Iterative compression (en)
- Итеративное сжатие (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
