Feedback arc set
http://dbpedia.org/resource/Feedback_arc_set an entity of type: WikicatComputationalProblemsInGraphTheory
Der Begriff Feedback Arc Set stammt aus der Graphentheorie und bezeichnet eine Menge von Kanten, durch deren Entfernung aus einem Graphen dieser azyklisch, d. h. kreisfrei wird.
rdf:langString
En théorie des graphes, un graphe orienté peut contenir des circuits, c'est-à-dire des chemins qui reviennent sur leur point de départ. Dans certaines applications, ces circuits sont indésirables, et on cherche à les éliminer pour obtenir un graphe orienté acyclique (souvent abrégé en DAG). Une façon de procéder est de simplement supprimer certains arcs du graphe pour couper les circuits. Un ensemble d'arcs de retour, ou coupe-cycles d'arcs communément appelé par son nom anglais un feedback arc set (FAS) est un ensemble d'arcs qui, lorsqu'il est supprimé du graphe, le transforme en graphe acyclique. Dit d'une autre manière, c'est un ensemble contenant au moins un arc de chaque circuit dans le graphe.
rdf:langString
In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing a directed acyclic graph, an acyclic subgraph of the given graph. The feedback arc set with the fewest possible edges is the minimum feedback arc set and its removal leaves the maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.
rdf:langString
В теории графов ориентированный граф может содержать ориентированные циклы, кольцо дуг, имеющих одно направление. В некоторых приложениях такие циклы нежелательны, мы можем исключить их и получить направленный ациклический граф (Directed Acyclic Graph, DAG). Один из способов исключения дуг — просто удаление дуг из графа. Разрезающий циклы набор дуг (Feedback Arc Set, FAS) или разрезающий циклы набор рёбер — это множество дуг, которые, при удалении их из графа, образуют DAG. Рассматривая под другим углом, это множество, содержащее по меньшей мере одно ребро из каждого цикла графа.
rdf:langString
Em teoria dos grafos, um grafo direcionado pode conter ciclos direcionados, um loop formado por um ciclo através de arestas. Em algumas aplicações, estes ciclos são indesejados, e queremos eliminá-los para obter um grafo acíclico direcionado (GAD). Uma maneira de fazer isso é simplesmente retirar arestas do grafo para remover os ciclos. Um conjunto de arcos de realimentação (CAR) ou conjunto de arestas de realimentação é um conjunto de arestas que, quando são retiradas do grafo, levam a um GAD. Em outras palavras é um conjunto que contém pelo menos uma aresta de cada ciclo existente no grafo.
rdf:langString
rdf:langString
Feedback Arc Set
rdf:langString
Feedback arc set
rdf:langString
Feedback arc set
rdf:langString
Conjunto de arcos de realimentação
rdf:langString
Разрезающий циклы набор рёбер
xsd:integer
1860374
xsd:integer
1121684055
rdf:langString
Der Begriff Feedback Arc Set stammt aus der Graphentheorie und bezeichnet eine Menge von Kanten, durch deren Entfernung aus einem Graphen dieser azyklisch, d. h. kreisfrei wird.
rdf:langString
In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing a directed acyclic graph, an acyclic subgraph of the given graph. The feedback arc set with the fewest possible edges is the minimum feedback arc set and its removal leaves the maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph. Feedback arc sets have applications in circuit analysis, chemical engineering, deadlock resolution, ranked voting, ranking competitors in sporting events, mathematical psychology, ethology, and graph drawing. Finding minimum feedback arc sets and maximum acyclic subgraphs is NP-hard; it can be solved exactly in exponential time, or in fixed-parameter tractable time. In polynomial time, the minimum feedback arc set can be approximated to within a polylogarithmic approximation ratio, and maximum acyclic subgraphs can be approximated to within a constant factor. Both are hard to approximate closer than some constant factor, an inapproximability result that can be strengthened under the unique games conjecture. For tournament graphs, the minimum feedback arc set can be approximated more accurately, and for planar graphs both problems can be solved exactly in polynomial time. A closely related problem, the feedback vertex set, is a set of vertices containing at least one vertex from every cycle in a directed or undirected graph. In undirected graphs, the spanning trees are the largest acyclic subgraphs, and the number of edges removed in forming a spanning tree is the circuit rank.
rdf:langString
En théorie des graphes, un graphe orienté peut contenir des circuits, c'est-à-dire des chemins qui reviennent sur leur point de départ. Dans certaines applications, ces circuits sont indésirables, et on cherche à les éliminer pour obtenir un graphe orienté acyclique (souvent abrégé en DAG). Une façon de procéder est de simplement supprimer certains arcs du graphe pour couper les circuits. Un ensemble d'arcs de retour, ou coupe-cycles d'arcs communément appelé par son nom anglais un feedback arc set (FAS) est un ensemble d'arcs qui, lorsqu'il est supprimé du graphe, le transforme en graphe acyclique. Dit d'une autre manière, c'est un ensemble contenant au moins un arc de chaque circuit dans le graphe.
rdf:langString
В теории графов ориентированный граф может содержать ориентированные циклы, кольцо дуг, имеющих одно направление. В некоторых приложениях такие циклы нежелательны, мы можем исключить их и получить направленный ациклический граф (Directed Acyclic Graph, DAG). Один из способов исключения дуг — просто удаление дуг из графа. Разрезающий циклы набор дуг (Feedback Arc Set, FAS) или разрезающий циклы набор рёбер — это множество дуг, которые, при удалении их из графа, образуют DAG. Рассматривая под другим углом, это множество, содержащее по меньшей мере одно ребро из каждого цикла графа. Тесно связанным понятием является разрезающее циклы множество вершин, в которое входит по меньшей мере по одной вершине из каждого цикла ориентированного графа, и минимальное остовное дерево, которое является неориентированным вариантом задачи нахождения разрезающего циклы набора дуг. Минимальный разрезающий циклы набор дуг (который нельзя уменьшить в размере удалением рёбер) имеет дополнительное свойство, что если в нём рёбра заменить на обратные, а не удалить, граф остаётся ациклическим. Нахождение небольшого множества рёбер с таким свойством является ключевым шагом в послойном рисунке графа . Иногда желательно отбросить как можно меньше дуг, образуя наименьший разрезающий циклы набор дуг, или двойственный наибольший ациклический подграф. Задача является сложной вычислительной задачей, для которой были разработаны некоторые аппроксимирующие решения.
rdf:langString
Em teoria dos grafos, um grafo direcionado pode conter ciclos direcionados, um loop formado por um ciclo através de arestas. Em algumas aplicações, estes ciclos são indesejados, e queremos eliminá-los para obter um grafo acíclico direcionado (GAD). Uma maneira de fazer isso é simplesmente retirar arestas do grafo para remover os ciclos. Um conjunto de arcos de realimentação (CAR) ou conjunto de arestas de realimentação é um conjunto de arestas que, quando são retiradas do grafo, levam a um GAD. Em outras palavras é um conjunto que contém pelo menos uma aresta de cada ciclo existente no grafo. Estreitamente relacionado é o conjunto de vértices de realimentação, que é um conjunto de vértices que contém ao menos um vértice de cada ciclo no grafo direcionado, e a árvore de extensão mínima, que é a forma não dirigida do problema do conjunto de arcos de realimentação. Um conjunto de arcos de realimentação mínimo (que não pode ser reduzido em tamanho por remoção de quaisquer arestas) tem a propriedade adicional de que, se as arestas forem invertidas ao invés de removidas, então o grafo permanece acíclico. Encontrar um pequeno conjunto de arestas com essa propriedade é um passo fundamental no desenho do grafo em camadas. Às vezes é desejável retirar tão poucas arestas quanto possível, obtendo um conjunto de arcos de realimentação mínimo, ou um subgrafo acíclico máximo. Isto é um problema computacional difícil, para o qual várias soluções aproximadas foram criadas.
xsd:nonNegativeInteger
54071
