This HTML5 document contains 113 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
n29http://www.cs.le.ac.uk/people/ir45/papers/
n16http://www.research.att.com/~mgcr/doc/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
n7https://global.dbpedia.org/id/
dbpedia-hehttp://he.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n8https://web.archive.org/web/20090920071048/http:/www.cs.huji.ac.il/~dinuri/mypapers/
owlhttp://www.w3.org/2002/07/owl#
n25https://archive.org/details/computersintract0000gare/page/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
n27http://www.cs.huji.ac.il/~dinuri/mypapers/
xsdhhttp://www.w3.org/2001/XMLSchema#
n5http://www.renyi.hu/~p_erdos/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Decomposition_method_(constraint_satisfaction)
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Robertson–Seymour_theorem
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Matroid_parity_problem
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Erdős–Pósa_theorem
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Feedback_arc_set
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Feedback_vertex_set
rdf:type
yago:Abstraction100002137 yago:Difficulty114408086 yago:Condition113920835 yago:Problem114410605 yago:State100024720 yago:WikicatComputationalProblemsInGraphTheory yago:Attribute100024264 yago:WikicatNP-completeProblems
rdfs:label
Разрезающее циклы множество вершин Feedback Vertex Set Conjunto de vértices de retroalimentação Coupe-cycles de sommets Feedback vertex set
rdfs:comment
Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP-vollständig ist. 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 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. В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа.Задача о разрезающем циклы множестве вершин является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС. 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.
dcterms:subject
dbc:Computational_problems_in_graph_theory dbc:NP-complete_problems
dbo:wikiPageID
1860368
dbo:wikiPageRevisionID
1100260536
dbo:wikiPageWikiLink
dbr:APX dbr:Journal_of_the_ACM dbr:Linear_matroid dbr:Vertex_cover dbr:Karp's_21_NP-complete_problems dbc:Computational_problems_in_graph_theory dbr:Component_(graph_theory) dbr:Deadlock dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:Algorithmica dbr:Decision_problem dbr:Spanning_tree dbr:Degree_(graph_theory) dbr:Canadian_Journal_of_Mathematics dbr:L-reduction dbr:Discrete_Mathematics_(journal) dbr:Journal_of_Artificial_Intelligence_Research dbr:NP_optimization_problem dbr:Artificial_Intelligence_(journal) dbr:VLSI dbr:Directed_graph dbr:Erdős–Pósa_theorem dbr:Graph_theory dbr:Matroid_parity_problem dbr:Cycle_(graph_theory) dbr:Directed_acyclic_graph dbr:Polynomial_time dbc:NP-complete_problems dbr:Circuit_rank dbr:Forest_(graph_theory) dbr:Feedback_arc_set dbr:Fixed-parameter_tractable dbr:Database_system dbr:Annals_of_Mathematics dbr:Wait-for_graph dbr:Operating_system dbr:Journal_of_Computer_and_System_Sciences dbr:Mathematics
dbo:wikiPageExternalLink
n5:1965-05.pdf n8:vc.pdf n16:sfsp.pdf n25: n27:vc.pdf n29:ictcsIgorCamera.pdf
owl:sameAs
n7:QaUf freebase:m.061sy6 dbpedia-pt:Conjunto_de_vértices_de_retroalimentação dbpedia-fr:Coupe-cycles_de_sommets dbpedia-fa:مجموعه_گره‌های_بازخورد dbpedia-ru:Разрезающее_циклы_множество_вершин dbpedia-hu:Körlefogó_csúcshalmaz dbpedia-de:Feedback_Vertex_Set yago-res:Feedback_vertex_set dbpedia-he:בעיית_קבוצת_קודקודי_המשוב wikidata:Q1400918
dbp:wikiPageUsesTemplate
dbt:Citation dbt:Harvtxt dbt:Sfnp dbt:Refend dbt:Reflist dbt:Refbegin
dbo:abstract
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. 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. Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP-vollständig ist. В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа.Задача о разрезающем циклы множестве вершин является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС. 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.
prov:wasDerivedFrom
wikipedia-en:Feedback_vertex_set?oldid=1100260536&ns=0
dbo:wikiPageLength
14717
foaf:isPrimaryTopicOf
wikipedia-en:Feedback_vertex_set
Subject Item
dbr:Kernelization
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Cycle_cutset
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
dbo:wikiPageRedirects
dbr:Feedback_vertex_set
Subject Item
dbr:Karp's_21_NP-complete_problems
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Cycle_graph
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Iterative_compression
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:List_of_NP-complete_problems
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Feedback_(disambiguation)
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
dbo:wikiPageDisambiguates
dbr:Feedback_vertex_set
Subject Item
dbr:Bidimensionality
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Directed_acyclic_graph
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Circuit_rank
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:List_of_terms_relating_to_algorithms_and_data_structures
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
Subject Item
dbr:Cycle_Cutset
dbo:wikiPageWikiLink
dbr:Feedback_vertex_set
dbo:wikiPageRedirects
dbr:Feedback_vertex_set
Subject Item
wikipedia-en:Feedback_vertex_set
foaf:primaryTopic
dbr:Feedback_vertex_set