Cograph (original) (raw)
In der Informatik ist ein Co-Graph ein ungerichteter Graph , welcher sich mit bestimmten elementaren Operationen konstruieren lässt. Auf Co-Graphen lassen sich viele schwere Probleme wie z. B. CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE sowie KNOTENÜBERDECKUNG in Linearzeit lösen.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union. Cographs have been discovered independently by several authors since the 1970s; early references include , , , and . They have also been called D*-graphs, hereditary Dacey graphs (after the related work of James C. Dacey Jr. on orthomodular lattices), and 2-parity graphs.They have a simple structural decomposition involving disjoint union and complement graph operations that can be represented concisely by a labeled tree, and used algorithmically to efficiently solve many problems such as finding the maximum clique that are hard on more general graph classes. Special cases of the cographs include the complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. The cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs. (en) In der Informatik ist ein Co-Graph ein ungerichteter Graph , welcher sich mit bestimmten elementaren Operationen konstruieren lässt. Auf Co-Graphen lassen sich viele schwere Probleme wie z. B. CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE sowie KNOTENÜBERDECKUNG in Linearzeit lösen. (de) Un cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud. La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles. (fr) Kograf (ang. cograph, P4-free graph) – graf, który można zbudować z pojedynczych wierzchołków za pomocą operacji oraz . Złączenie grafów G i F to graf powstały poprzez połączenie wszystkich wierzchołków grafu G z wszystkimi wierzchołkami grafu F, przy zachowaniu wewnętrznej budowy grafów G i F. Natomiast operacja sumy grafów to zwykłe sumowanie zbiorów krawędzi i wierzchołków. Kografy można wygodnie reprezentować za pomocą (ang. cotree), którego liśćmi są wierzchołki grafów, natomiast węzły wewnętrzne drzewa reprezentują operację złączenia (1) i sumowania (0). (pl) В теорії графів кограф, або додатково звідний граф, чи граф, вільний від P4, — це граф, який можна отримати з графа з єдиною вершиною K1 операціями доповнення та об'єднання графів. Таким чином, сімейство кографів — це найменший клас графів, що містить K1 і замкнутий відносно доповнення та об'єднання. Кографи відкривали незалежно кілька авторів, починаючи від 1970-х років. Найраніші згадки можна знайти у Янга, Лерчса, Зайнше і . Ці графи називали D*-графами, спадковими графами Дейсі (після роботи Джеймса Дейсі (James C. Dacey, Jr.) про . Див. роботу Самнера) та графи з двома нащадками Барлета і Урі. В книзі Брандштедта, Лі і Шпінрада кографи розглянуто детальніше, включно з фактами, наведеними тут. (uk) В теории графов кограф, или дополнительно сводимый граф, или граф, свободный от P4, — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов. Таким образом, семейство кографов — это наименьший класс графов, содержащий K1 и замкнутый относительно дополнения и объединения. Кографы открывались независимо несколькими авторами, начиная с 1970-х годов. Самые ранние упоминания можно найти у Янга, Лерчса, Зайнше и Самнера. Эти графы назывались D*-графами, наследственными графами Дейси (после работы Джеймса Дейси [James C. Dacey, Jr.] об . Смотрите работу Самнера) и графы с двумя потомками Барлета и Ури. Смотрите книгу Брандштедта, Ли и Шпинрада, где кографы рассмотрены более детально, включая факты, приведённые здесь. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Turan_13-4.svg?width=300 |
| dbo:wikiPageExternalLink | https://archive.org/details/graphclassessurv0000bran http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf http://www.lirmm.fr/~paul/Biblio/Postscript/DAM-cographs.pdf http://www.graphclasses.org https://digitalcommons.odu.edu/computerscience_fac_pubs/122 http://www.graphclasses.org/classes/gc_151.html |
| dbo:wikiPageID | 1175666 (xsd:integer) |
| dbo:wikiPageLength | 21893 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1110999582 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Binary_relation dbc:Graph_families dbc:Perfect_graphs dbr:Induced_path dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Maximal_independent_set dbr:Clique-width dbr:Clique_problem dbr:Cluster_graph dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Ordinal_sum dbr:Logic_of_graphs dbr:Lowest_common_ancestor dbr:Chordal_completion dbr:Shortest_path dbr:Clique_(graph_theory) dbr:Comparability_graph dbr:Complement_graph dbr:Hamiltonian_path_problem dbr:Kruskal's_tree_theorem dbr:Path_(graph_theory) dbr:Perfect_graph dbr:Trivially_perfect_graph dbr:Well-quasi-ordering dbr:Disjoint_union_of_graphs dbr:Separable_permutation dbr:Forbidden_graph_characterization dbr:Partition_refinement dbr:Discrete_Applied_Mathematics dbr:Graph_isomorphism dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_Graph_Theory dbr:Courcelle's_theorem dbc:Graph_operations dbr:Hereditary_property dbr:Threshold_graph dbr:Modular_decomposition dbr:Disjoint_union dbr:Distance-hereditary_graph dbr:Distance_(graph_theory) dbr:Planar_graph dbr:Connected_component_(graph_theory) dbr:Greedy_coloring dbr:Grundy_number dbr:Read-once_function dbr:Series-parallel_partial_order dbr:Maximum_clique dbr:Perfectly_orderable_graph dbr:Permutation_graph dbr:Parameterized_complexity dbr:Turán_graph dbr:Orthomodular_lattice dbr:LexBFS dbr:Split_decomposition dbr:Strongly_perfect_graph dbr:File:Cotree_and_cograph.svg dbr:File:Turan_13-4.svg |
| dbp:mode | cs2 (en) |
| dbp:title | Cograph (en) |
| dbp:urlname | Cograph (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Math dbt:Mathworld dbt:Mvar dbt:OEIS dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description |
| dcterms:subject | dbc:Graph_families dbc:Perfect_graphs dbc:Graph_operations |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Action114006945 yago:Attribute100024264 yago:Communication100033020 yago:Graph107000195 yago:Operation114008806 yago:WikicatGraphOperations yago:State100024720 yago:VisualCommunication106873252 yago:WikicatPerfectGraphs |
| rdfs:comment | In der Informatik ist ein Co-Graph ein ungerichteter Graph , welcher sich mit bestimmten elementaren Operationen konstruieren lässt. Auf Co-Graphen lassen sich viele schwere Probleme wie z. B. CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE sowie KNOTENÜBERDECKUNG in Linearzeit lösen. (de) Un cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud. La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles. (fr) Kograf (ang. cograph, P4-free graph) – graf, który można zbudować z pojedynczych wierzchołków za pomocą operacji oraz . Złączenie grafów G i F to graf powstały poprzez połączenie wszystkich wierzchołków grafu G z wszystkimi wierzchołkami grafu F, przy zachowaniu wewnętrznej budowy grafów G i F. Natomiast operacja sumy grafów to zwykłe sumowanie zbiorów krawędzi i wierzchołków. Kografy można wygodnie reprezentować za pomocą (ang. cotree), którego liśćmi są wierzchołki grafów, natomiast węzły wewnętrzne drzewa reprezentują operację złączenia (1) i sumowania (0). (pl) In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union. Special cases of the cographs include the complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. The cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs. (en) В теорії графів кограф, або додатково звідний граф, чи граф, вільний від P4, — це граф, який можна отримати з графа з єдиною вершиною K1 операціями доповнення та об'єднання графів. Таким чином, сімейство кографів — це найменший клас графів, що містить K1 і замкнутий відносно доповнення та об'єднання. В книзі Брандштедта, Лі і Шпінрада кографи розглянуто детальніше, включно з фактами, наведеними тут. (uk) В теории графов кограф, или дополнительно сводимый граф, или граф, свободный от P4, — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов. Таким образом, семейство кографов — это наименьший класс графов, содержащий K1 и замкнутый относительно дополнения и объединения. Смотрите книгу Брандштедта, Ли и Шпинрада, где кографы рассмотрены более детально, включая факты, приведённые здесь. (ru) |
| rdfs:label | Cograph (en) Co-Graph (de) Cographe (fr) Kograf (pl) Кограф (ru) Кограф (uk) |
| owl:sameAs | freebase:Cograph yago-res:Cograph wikidata:Cograph dbpedia-de:Cograph dbpedia-fr:Cograph dbpedia-he:Cograph dbpedia-hu:Cograph dbpedia-pl:Cograph dbpedia-ru:Cograph dbpedia-uk:Cograph https://global.dbpedia.org/id/4iFmS |
| prov:wasDerivedFrom | wikipedia-en:Cograph?oldid=1110999582&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Cotree_and_cograph.svg wiki-commons:Special:FilePath/Turan_13-4.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Cograph |
| is dbo:wikiPageRedirects of | dbr:Cotree dbr:P4-free_graph dbr:P4_free_graph dbr:P_4-free_graph dbr:P_4_free_graph dbr:Co-graph dbr:Complement-reducible_graph dbr:Complement_reducible_graph |
| is dbo:wikiPageWikiLink of | dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Derek_Corneil dbr:Independent_set_(graph_theory) dbr:Induced_path dbr:Lexicographic_breadth-first_search dbr:Well-colored_graph dbr:Complete_coloring dbr:Maximal_independent_set dbr:Radio_coloring dbr:Chromatic_polynomial dbr:Clique-width dbr:Cluster_graph dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Multipartite_graph dbr:Erdős–Hajnal_conjecture dbr:Chordal_completion dbr:Clique_(graph_theory) dbr:Clique_cover dbr:Comparability_graph dbr:Complement_graph dbr:Perfect_graph dbr:Trivially_perfect_graph dbr:Well-quasi-ordering dbr:Disjoint_union_of_graphs dbr:Cotree dbr:Separable_permutation dbr:Forbidden_graph_characterization dbr:Hanner_polytope dbr:Chordal_graph dbr:Threshold_graph dbr:Modular_decomposition dbr:Distance-hereditary_graph dbr:Split_graph dbr:Greedy_coloring dbr:Grundy_number dbr:Implicit_graph dbr:Metric_dimension_(graph_theory) dbr:Read-once_function dbr:Series-parallel_partial_order dbr:Lorna_Stewart dbr:Series–parallel_graph dbr:Perfectly_orderable_graph dbr:Permutation_graph dbr:Subcoloring dbr:Turán_graph dbr:Twin-width dbr:P4-free_graph dbr:P4_free_graph dbr:P_4-free_graph dbr:P_4_free_graph dbr:Co-graph dbr:Complement-reducible_graph dbr:Complement_reducible_graph |
| is foaf:primaryTopic of | wikipedia-en:Cograph |
