Feedback vertex set (original) (raw)
Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP-vollständig ist.
| Property | Value |
|---|---|
| dbo:abstract | Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP-vollständig ist. (de) In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles ("removal" means deleting the vertex and all edges adjacent to it). Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design. (en) En théorie des graphes, un coupe-cycles de sommets, ou feedback vertex set en anglais, est un ensemble de sommets d'un graphe, tel que le retrait de ces nœuds laisse le graphe acyclique. Autrement dit, c'est un ensemble de nœuds ayant une intersection non nulle avec chaque cycle. Le problème du coupe-cycle de sommets, est un problème algorithmique d'optimisation combinatoire, qui consiste à trouver un coupe-cycles de sommets de taille minimum. (fr) Dentro da disciplina de teoria dos grafos, um conjunto de vértices de retroalimentação de um grafo é um conjunto de vértices cujas folhas removíveis deixam o grafo sem ciclo. Em outra palavras, cada conjunto de vértices retroativos contém pelo menos um vértice contido em algum ciclo no grafo. O problema dos conjuntos de vértices retroativos é um problema NP-completo em complexidade computacional. Ele estava presente nos 21 problemas NP-completos de Karp. O conjunto de vértices de retroalimentação possui várias aplicações em sistemas operacionais, sistemas de banco de dados, montagem de genoma (criação de cromossomos artificiais) e no design de chips. (pt) В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа.Задача о разрезающем циклы множестве вершин является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС. (ru) |
| dbo:wikiPageExternalLink | http://www.research.att.com/~mgcr/doc/sfsp.pdf http://www.cs.le.ac.uk/people/ir45/papers/ictcsIgorCamera.pdf https://archive.org/details/computersintract0000gare/page/ https://web.archive.org/web/20090920071048/http:/www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf http://www.renyi.hu/~p_erdos/1965-05.pdf http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf |
| dbo:wikiPageID | 1860368 (xsd:integer) |
| dbo:wikiPageLength | 14717 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1100260536 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithmica dbr:Annals_of_Mathematics dbr:Cycle_(graph_theory) dbr:VLSI dbr:Vertex_cover dbr:Deadlock dbr:Decision_problem dbr:Degree_(graph_theory) dbr:L-reduction dbc:NP-complete_problems dbr:Mathematics dbr:Matroid_parity_problem dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:Erdős–Pósa_theorem dbr:Component_(graph_theory) dbr:Feedback_arc_set dbr:Database_system dbr:Journal_of_Artificial_Intelligence_Research dbr:Spanning_tree dbr:Karp's_21_NP-complete_problems dbr:Directed_graph dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Journal_of_Computer_and_System_Sciences dbr:Journal_of_the_ACM dbr:Fixed-parameter_tractable dbr:APX dbc:Computational_problems_in_graph_theory dbr:Directed_acyclic_graph dbr:Artificial_Intelligence_(journal) dbr:Circuit_rank dbr:Polynomial_time dbr:Operating_system dbr:Canadian_Journal_of_Mathematics dbr:Forest_(graph_theory) dbr:Wait-for_graph dbr:Linear_matroid dbr:NP_optimization_problem |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp |
| dct:subject | dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory |
| rdf:type | yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 |
| rdfs:comment | Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP-vollständig ist. (de) In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles ("removal" means deleting the vertex and all edges adjacent to it). Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design. (en) En théorie des graphes, un coupe-cycles de sommets, ou feedback vertex set en anglais, est un ensemble de sommets d'un graphe, tel que le retrait de ces nœuds laisse le graphe acyclique. Autrement dit, c'est un ensemble de nœuds ayant une intersection non nulle avec chaque cycle. Le problème du coupe-cycle de sommets, est un problème algorithmique d'optimisation combinatoire, qui consiste à trouver un coupe-cycles de sommets de taille minimum. (fr) В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа.Задача о разрезающем циклы множестве вершин является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС. (ru) Dentro da disciplina de teoria dos grafos, um conjunto de vértices de retroalimentação de um grafo é um conjunto de vértices cujas folhas removíveis deixam o grafo sem ciclo. Em outra palavras, cada conjunto de vértices retroativos contém pelo menos um vértice contido em algum ciclo no grafo. O problema dos conjuntos de vértices retroativos é um problema NP-completo em complexidade computacional. Ele estava presente nos 21 problemas NP-completos de Karp. (pt) |
| rdfs:label | Feedback Vertex Set (de) Feedback vertex set (en) Coupe-cycles de sommets (fr) Conjunto de vértices de retroalimentação (pt) Разрезающее циклы множество вершин (ru) |
| owl:sameAs | freebase:Feedback vertex set wikidata:Feedback vertex set dbpedia-de:Feedback vertex set dbpedia-fa:Feedback vertex set dbpedia-fr:Feedback vertex set dbpedia-he:Feedback vertex set dbpedia-hu:Feedback vertex set dbpedia-pt:Feedback vertex set dbpedia-ru:Feedback vertex set https://global.dbpedia.org/id/QaUf yago-res:Feedback vertex set |
| prov:wasDerivedFrom | wikipedia-en:Feedback_vertex_set?oldid=1100260536&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Feedback_vertex_set |
| is dbo:wikiPageDisambiguates of | dbr:Feedback_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Cycle_cutset dbr:Cycle_Cutset |
| is dbo:wikiPageWikiLink of | dbr:Decomposition_method_(constraint_satisfaction) dbr:Robertson–Seymour_theorem dbr:Matroid_parity_problem dbr:Erdős–Pósa_theorem dbr:Feedback_arc_set dbr:Kernelization dbr:Cycle_cutset dbr:Karp's_21_NP-complete_problems dbr:Cycle_graph dbr:Iterative_compression dbr:List_of_NP-complete_problems dbr:Feedback_(disambiguation) dbr:Bidimensionality dbr:Directed_acyclic_graph dbr:Circuit_rank dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Cycle_Cutset |
| is foaf:primaryTopic of | wikipedia-en:Feedback_vertex_set |