acyclic digraph
Hello, you have come here looking for the meaning of the word acyclic digraph. In DICTIOUS you will not only get to know all the dictionary meanings for the word acyclic digraph, but we will also tell you about its etymology, its characteristics and you will know how to say acyclic digraph in singular and plural. Everything you need to know about the word acyclic digraph you have here. The definition of the word acyclic digraph will help you to be more precise and correct when speaking or writing your texts. Knowing the definition ofacyclic digraph, as well as those of other words, enriches your vocabulary and provides you with more and better linguistic resources.
English
Pronunciation
Noun
acyclic digraph (plural acyclic digraphs)
- (graph theory, computer science) A directed acyclic graph, a finite directed graph that contains no directed cycles.
- 1993, Suh-Ryung-Kim, The Competition Number and Its Variants, J. Gimbel, J.W. Kennedy, L.V. Quintas (editors), Quo Vadis, Graph Theory?: A Source Book for Challenges and Directions, Elsevier (North-Holland), page 313,
- In the study of the competition graph of an acyclic digraph, there are two fundamental questions which were proposed by Roberts in 1978: One is to characterize the acyclic digraphs that have interval competition graphs and the other is to characterize the graphs which are competition graphs of acyclic digraphs.
- 2009, Tamara Mchedlidze, Antonios Symvonis, Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs, Hung Q. Ngo (editor), Computing and Combinatorics: 15th Annual International Conference, Proceedings, Springer, LNCS 5609, page 76,
- Determining whether a graph has a hamiltonian path or circuit is NP-complete . The problem remains NP-complete for cubic planar graphs , for maximal planar graphs , and for planar digraphs . It can be trivially solved in polynomial time for planar acyclic digraphs.
- 2018, Gregory Gutin, 3. Acyclic Digraphs, Jørgen Bang-Jensen, Gregory Gutin, Classes of Directed Graphs, Springer, page 125,
- Acyclic digraphs form a well-studied family of digraphs of great interest in graph theory, algorithms and applications.
- 1993, Suh-Ryung-Kim, The Competition Number and Its Variants, J. Gimbel, J.W. Kennedy, L.V. Quintas (editors), Quo Vadis, Graph Theory?: A Source Book for Challenges and Directions, Elsevier (North-Holland), page 313,
Synonyms
- (directed graph without cycles): acyclic directed graph, directed acyclic graph (DAG)
Translations
directed acyclic graph — see directed acyclic graph