Dubbla ackordsdiagram

En oriktad graf G är dubbelkordal om dess maximala klickhypergraf är ett hyperträd . Namnet kommer från det faktum att en graf är kordal om och endast om dess maximala klickhypergraf är dubbel till ett hyperträd. Dessa grafer definierades ursprungligen av maximal grannskap och har ett antal olika beskrivningar [1] [2] [3] . Till skillnad från ackordsgrafer ärvs inte egenskapen dubbel ackordalitet, det vill säga de genererade subgraferna i en dubbel ackordgraf är inte nödvändigtvis dubbla ackordala (i betydelsen arv är dubbla ackordsgrafer exakt efterföljare av strikt ackordsgrafer ), och en Dual chordal graph är inte perfekt i allmänhet . Dubbla ackordsgrafer dök till en början under namnet HT-grafer [4] [5] [6] .

Beskrivning

Dubbla ackordsgrafer är klickgrafer av ackordsgrafer [7] [8] , det vill säga skärningsgrafer för maximala klicker av ackordsgrafer.

Följande egenskaper motsvarar [1] [2] [9] [5] [6] :

Det följer också av villkoret på en hypergraf med stängt grannskap att en graf är dubbelkordal om och endast om dess kvadrat är kordal och dess hypergraf för sluten grannskap har egenskapen Helly .

Artikeln av De Caria och Gutirrez [11] beskriver dubbla kordalgrafer i termer av egenskaper hos separatorer. Det visades i Breshards artikel [12] att dubbla kordalgrafer är exakt skärningsgraferna för maximala hyperkuber av grafer för acykliska kubiska komplex.

Strukturen och den algoritmiska användningen av dubbla ackordsgrafer gavs av Marina Moscarini [13] . Dessa är ackordsgrafer som är samtidigt och dubbelt ackordala.

Erkännande

Dubbla ackordsgrafer kan kännas igen i linjär tid, och ordningen för det maximala grannskapet för en dubbla ackordsgraf kan hittas i linjär tid [2] [4] .

Problemens komplexitet

Medan grundläggande problem som att hitta den maximala oberoende uppsättningen , maximal klick , färgning och klicktäckning förblir NP-kompletta för dubbla ackordsgrafer, är vissa varianter av Steiners minimala dominerande set och trädproblem effektivt lösta för dubbla ackordsgrafer (men de oberoende dominans förblir NP-komplett ) [2] [5] [6] . Se Branstadt, Chepoy och Dragan [14] för att använda egenskaperna hos dubbla ackordsgrafer för spännträdsproblem, och Branstadt, Leitert och Rautenbach [15] för den linjära tidsvertex- och kantdominansalgoritmen.

Anteckningar

  1. ↑ 1 2 Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // Föreläsningsanteckningar i datavetenskap . - 1993. - T. 790 . — S. 237–251 .
  2. ↑ 1 2 3 4 Andreas Brandstädt, Victor Chepoi, Feodor Dragan. Algoritmisk användning av hyperträdstruktur och maximal grannskapsordning // Diskret tillämpad matematik . - 1998. - T. 82 . — s. 43–77 . - doi : 10.1016/s0166-218x(97)00125-x .
  3. ↑ Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Grafklasser: En undersökning. - SIAM Monographs on Discrete Mathematics and Applications, 1999. - ISBN 0-89871-432-X .
  4. ↑ 1 2 Feodor Dragan. Centers of Graphs and the Helly Property (på ryska). – Ph.D. avhandling, Moldova State University, Moldavien, 1989.
  5. ↑ 1 2 3 Feodor Dragan, Chiril Prisacaru, Victor Chepoi. Platsproblem i grafer och Helly-egenskapen // Discrete Math. (Moskva) . - 1992. - T. 4 . — s. 67–73 . ; F. F. Dragan, K. F. Prisakar, V. D. Chepoy. Lokaliseringsproblem på grafer och Helly-fastigheten  // Diskret. Mat.. - 1992. - V. 4 , nr. 4 . — s. 67–73 . ; Fedor Fedorovich Dragan. Centrerar i grafer och Helly-egenskapen. - Minsk: BSSR:s vetenskapsakademi. Institutet för matematik, 1989. - (Författarens sammandrag av Kandidat för fysikaliska och matematiska vetenskaper: 01.01.09).
  6. ↑ 1 2 3 Feodor Dragan. HT-grafer: centra, ansluten r-domination och Steiner-träd // Comput. sci. J. av Moldavien (Kishinev) . - 1993. - T. 1 . — S. 64–83 .
  7. ↑ Marisa Gutierrez, Oubina. Metriska karaktäriseringar av korrekta intervallgrafer och trädklicksgrafer  // Journal of Graph Theory . - 1996. - T. 21 . — S. 199–205 . - doi : 10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m .
  8. ↑ Jayme L. Szwarcfiter, Claudson F. Bornstein. Clique Graphs of Chordal and Path Graphs // SIAM Journal on Discrete Mathematics . - 1994. - T. 7 . — S. 331–336 . - doi : 10.1137/s0895480191223191 .
  9. ↑ Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // SIAM Journal on Discrete Mathematics . - 1998. - T. 11 . — S. 437–455 . - doi : 10.1137/s0895480193253415 .
  10. ↑ Konceptet med att beställa det maximala grannskapet är inte trivialt, i artikeln (Brandstädt, Dragan, Chepoi, Voloshin, 1998, s. 440-442) tar det 2 sidor
  11. ↑ Pablo De Caria, Marisa Gutierrez. På Minimal Vertex Separators of Dually Chordal Graphs: Properties and Characterizations // Discrete Applied Mathematics . - 2012. - T. 160 . — S. 2627–2635 . - doi : 10.1016/j.dam.2012.02.022 .
  12. ↑ Bostjan Bresar. Skärningsdiagram för maximala hyperkuber // European Journal of Combinatorics . - 2003. - T. \u003d 24 . — S. 195–209 . - doi : 10.1016/s0195-6698(02)00142-7 .
  13. ↑ Marina Moscarini. Dubbla kordalgrafer, Steinerträd och ansluten dominans  // Nätverk. - 1993. - T. 23 . — s. 59–69 . - doi : 10.1002/net.3230230108 .
  14. ↑ Andreas Brandstädt, Victor Chepoi, Feodor Dragan. Avståndsapproximerande träd för ackords- och dualchordal-grafer // Journal of Algorithms . - 1999. - T. 30 . — S. 166–184 . - doi : 10.1006/jagm.1998.0962 .
  15. ↑ Andreas Brandstädt, Arne Leitert, Dieter Rautenbach. Effektiva dominerande och kantdominerande set för grafer och hypergrafer // Föreläsningsanteckningar i datavetenskap . - 2012. - T. 7676 . — S. 267–277 .

Litteratur