Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Iterative_compression> ?p ?o }
Showing triples 1 to 39 of
39
with 100 triples per page.
- Iterative_compression 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 odd cycle transversal was solvable in time O(3k kmn), for a graph with n vertices, m edges, and odd cycle traversal 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.".
- Iterative_compression wikiPageID "46386066".
- Iterative_compression wikiPageLength "8676".
- Iterative_compression wikiPageOutDegree "22".
- Iterative_compression wikiPageRevisionID "700892062".
- Iterative_compression wikiPageWikiLink Algorithm.
- Iterative_compression wikiPageWikiLink Bipartite_graph.
- Iterative_compression wikiPageWikiLink Category:Analysis_of_algorithms.
- Iterative_compression wikiPageWikiLink Category:Graph_algorithms.
- Iterative_compression wikiPageWikiLink Category:Parameterized_complexity.
- Iterative_compression wikiPageWikiLink Computer_science.
- Iterative_compression wikiPageWikiLink Exponential_search.
- Iterative_compression wikiPageWikiLink Feedback_vertex_set.
- Iterative_compression wikiPageWikiLink Graph_theory.
- Iterative_compression wikiPageWikiLink Independent_set_(graph_theory).
- Iterative_compression wikiPageWikiLink Induced_subgraph.
- Iterative_compression wikiPageWikiLink Kernelization.
- Iterative_compression wikiPageWikiLink Linear_search.
- Iterative_compression wikiPageWikiLink Max-flow_min-cut_theorem.
- Iterative_compression wikiPageWikiLink Natural_number.
- Iterative_compression wikiPageWikiLink Parameterized_complexity.
- Iterative_compression wikiPageWikiLink Time_complexity.
- Iterative_compression wikiPageWikiLink Vertex_(graph_theory).
- Iterative_compression wikiPageWikiLink Vertex_cover.
- Iterative_compression wikiPageWikiLinkText "Iterative compression".
- Iterative_compression wikiPageWikiLinkText "iterative compression".
- Iterative_compression wikiPageUsesTemplate Template:Math.
- Iterative_compression wikiPageUsesTemplate Template:Mvar.
- Iterative_compression wikiPageUsesTemplate Template:Reflist.
- Iterative_compression subject Category:Analysis_of_algorithms.
- Iterative_compression subject Category:Graph_algorithms.
- Iterative_compression subject Category:Parameterized_complexity.
- Iterative_compression hypernym Technique.
- Iterative_compression type TopicalConcept.
- Iterative_compression comment "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 odd cycle transversal was solvable in time O(3k kmn), for a graph with n vertices, m edges, and odd cycle traversal number k. ".
- Iterative_compression label "Iterative compression".
- Iterative_compression sameAs m.013378_1.
- Iterative_compression wasDerivedFrom Iterative_compression?oldid=700892062.
- Iterative_compression isPrimaryTopicOf Iterative_compression.