Starkt ackorddiagram - Strongly chordal graph

I matematisk yta på grafteori , en oriktad graf G är starkt ackord om det är en ackord graf och varje cykel av jämn längd (≥ 6) i G har ett udda ackord , dvs en kant som förbinder två hörn som är en udda avstånd (> 1) från varandra i cykeln.

Karaktäriseringar

Starkt ackordala grafer har en förbjuden karaktärisering av undergrafer som grafer som inte innehåller en inducerad cykel med en längd som är större än tre eller en n- sol ( n  ≥ 3) som en inducerad subgraf . En n -sol är ett ackorddiagram med 2 n hörn, uppdelat i två delmängder U  = { u 1 ,  u 2 , ...} och W  = { w 1 ,  w 2 , ...}, så att varje toppunkt w jag i W har exakt två grannar, u i och u ( i  + 1) mod  n . En n -sol kan inte vara starkt ackordal, eftersom cykeln u 1 w 1 u 2 w 2 ... inte har något udda ackord.

Starkt ackorddiagram kan också karaktäriseras som graferna som har en stark perfekt eliminationsordning, en ordning av topparna så att grannarna till varje toppunkt som kommer senare i ordningen bildar en klick och sådan att för varje i  <  j  <  k  <  l , om jag : te vertex i beställnings ligger i anslutning till k : te och l : te hörn, och den j : te och k : te hörn är intill, då j : te och l : te hörn måste också vara angränsande.

En graf är starkt ackordal om och bara om var och en av dess inducerade underbilder har ett enkelt toppunkt, ett toppunkt vars grannar har kvarter som är linjärt ordnade genom inkludering. En graf är också starkt ackordal om och bara om den är ackordal och varje cykel med längd fem eller mer har en tvåakkordstriangel, en triangel bildad av två ackord och en kant av cykeln.

En graf är starkt ackordal om och bara om vart och ett av dess inducerade underbilder är ett dubbelt ackorddiagram .

Starkt ackorddiagram kan också karaktäriseras i termer av antalet kompletta underbilder varje kant deltar i. Ytterligare en annan karaktärisering ges i.

Erkännande

Det är möjligt att avgöra om ett diagram är starkt ackordalt i polynomtid genom att upprepade gånger söka efter och ta bort ett enkelt toppunkt. Om denna process eliminerar alla hörn i diagrammet, måste diagrammet vara starkt ackordalt; I annat fall, om den här processen hittar en subgraf utan mer enkla hörn, kan den ursprungliga grafen inte vara starkt ackordal. För ett starkt ackorddiagram är ordningen i vilken topparna tas bort genom denna process en stark perfekt eliminationsordning.

Alternativa algoritmer är nu kända som kan avgöra om ett diagram är starkt ackordalt och, om så är fallet, konstruera en stark perfekt eliminering som beställer mer effektivt, i tid O (min ( n 2 , ( n + m ) log n )) för en graf med n hörn och m kanter.

Underklasser

En viktig underklass (baserad på fylogeni ) är klassen av k - lövkrafter , graferna bildas från ett träds löv genom att förbinda två blad med en kant när deras avstånd i trädet högst är k . En bladeffekt är ett diagram som är en k- bladeffekt för vissa k . Eftersom kraften i starkt ackordala diagram är starkt ackordal och träd är starkt ackordal, följer det att bladkrafter är starkt ackordala. De bildar en ordentlig underklass av starkt ackorddiagram, som i sin tur inkluderar klusterdiagrammen som tvåbladiga krafter. En annan viktig underklass med starkt ackorddiagram är intervalldiagram . I det visas att intervalldiagram och den större klassen rotade riktade bandiagram är bladkrafter.

Algoritmiska problem

Eftersom starka ackorddiagram är både ackorddiagram och dubbelt ackorddiagram , kan olika NP-kompletta problem som Independent Set, Clique, Coloring, Clique Cover, Dominating Set och Steiner Tree lösas effektivt för starkt ackorddiagram. Grafisomorfism är isomorfism komplett för starkt ackordala grafer. Hamiltonian Circuit förblir NP-komplett för starkt delade grafer .

Anteckningar

Referenser

  • Brandstädt, Andreas ; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics , 11 (3): 437–455, doi : 10.1137 / s0895480193253415.
  • Brandstädt, Andreas ; Hundt, kristen; Mancini, Federico; Wagner, Peter (2010), "Rotade riktade vägdiagram är bladkrafter", Diskret matematik , 310 (4): 897–910, doi : 10.1016 / j.disc.2009.10.006.
  • Brandstädt, Andreas ; Le, Van Bang (2006), "Struktur och linjär tidsigenkänning av trebladiga krafter", Information Processing Letters , 98 (4): 133–138, doi : 10.1016 / j.ipl.2006.01.004.
  • Brandstädt, Andreas ; Le, Van Bang; Sritharan, R. (2008), "Struktur och linjär tidsigenkänning av fyrbladiga krafter", ACM-transaktioner på algoritmer , 5 : artikel 11, doi : 10.1145 / 1435375.1435386.
  • Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Grafklasser: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Chang, GJ (1982), K -domination och diagramtäckningsproblem , Ph.D. avhandling, Cornell University.
  • Dahlhaus, E .; Manuel, PD; Miller, M. (1998), "A characterization of starkt chordal charts", Discrete Mathematics , 187 (1–3): 269–271, doi : 10.1016 / S0012-365X (97) 00268-9.
  • De Caria, P .; McKee, TA (2014), "Maxclique och enhetsskivkaraktäriseringar av starkt ackordiska grafer", Discussiones Mathematicae Graph Theory , 34 (3): 593–602, doi : 10.7151 / dmgt.1757.
  • Farber, M. (1983), "Karaktäriseringar av starkt ackorddiagram", Diskret matematik , 43 (2–3): 173–189, doi : 10.1016 / 0012-365X (83) 90154-1.
  • Lubiw, A. (1987), "Dubbel lexikalisk ordning av matriser", SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137 / 0216057.
  • McKee, TA (1999), "En ny karaktärisering av starkt ackorddiagram", Diskret matematik , 205 (1–3): 245–247, doi : 10.1016 / S0012-365X (99) 00107-7.
  • Müller, H. (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", Discrete Mathematics , 156 (1–3): 291–298, doi : 10.1016 / 0012-365x (95) 00057-4.
  • Nishimura, N .; Ragde, P .; Thilikos, DM (2002), "On graf befogenheter för bladmärkta träd", Journal of Algorithms , 42 : 69-108, doi : 10,1006 / jagm.2001.1195.
  • Paige, R .; Tarjan, RE (1987), "Three partition refinement algorithms", SIAM Journal on Computing , 16 (6): 973–989, doi : 10.1137 / 0216062.
  • Rautenbach, D. (2006), "Några kommentarer om bladrötter", Diskret matematik , 306 (13): 1456–1461, doi : 10.1016 / j.disc.2006.03.030.
  • Spinrad, J. (1993), "Dubbel lexikal ordning av täta 0-1 matriser", Information Processing Letters , 45 (2): 229-235, doi : 10.1016 / 0020-0190 (93) 90209-R.
  • Uehara, R .; Toda, S .; Nagoya, T. (2005), "Graph isomorphism completeeness for chordal bipartite and starkt chordal charts", Discrete Applied Mathematics , 145 (3): 479–482, doi : 10.1016 / j.dam.2004.06.008.