Bladkraft - Leaf power
I det matematiska området för grafteori är en k- bladkraft hos ett träd en graf vars hörn är bladen av och vars kanter förbinder par av löv vars avstånd är högst . Det vill säga är en inducerad subgraf av grafkraften , inducerad av bladen av . För en graf konstruerad på detta sätt kallas en k- bladrot av .
En graf är ett blad makt om det är en -leaf kraft för vissa . Dessa diagram har tillämpningar i fylogeni , problemet med att rekonstruera evolutionära träd.
Relaterade klasser av diagram
Eftersom kraften i starkt ackordiska grafer är starkt ackordal och träd är starkt ackordal, följer det att bladkrafter är starkt ackorddiagram. Egentligen bildar bladkrafter en ordentlig underklass av starkt ackordala grafer; ett diagram är en bladeffekt om och endast om det är en fast tolerans NeST-graf och sådana grafer är en riktig underklass av starkt ackorddiagram.
I Brandstädt et al. (2010) visas att intervalldiagram och den större klassen rotade riktade bandiagram är bladkrafter. De likgiltighet kurvor är exakt blad befogenheter vars underliggande träd är larv träd .
Den k -leaf befogenheter avgränsas värden av k Ha avgränsat klicken bredd , men detta är inte fallet med blad befogenheter med obegränsad exponenter.
Struktur och erkännande
Finns det en polynom- tidsalgoritm för att känna igen bladkrafter eller -bladkrafter för ?
Ett diagram är en tvåbladig kraft om och endast om det är den ojämna sammansättningen av klick (dvs. ett klusterdiagram ).
En graf är en trebladig kraft om och bara om det är ett (tjur, dart, pärla) -fritt ackorddiagram . Baserat på denna karaktärisering och liknande kan 3-bladskrafter kännas igen linjärt .
Karaktäriseringar av fyrbladiga krafter ges av Rautenbach (2006) och Brandstädt, Le & Sritharan (2008) , vilket också möjliggör linjär tidsigenkänning. Erkännande av effektblad för 5-blad och 6-blad löses också linjärt av Chang respektive Ko (2007) respektive Ducoffe (2018).
För ≥ 7 är erkännandeproblemet med bladkrafter öppet, och på samma sätt är det ett öppet problem om bladkrafter kan kännas igen i polynomtid . Det har emellertid visat sig att igenkänning av -bladkrafter kan fastställas med parametrar när den parametreras av och inmatningsdiagrammets degenerering .
Anteckningar
Referenser
- Bibelnieks, E .; Dearing, PM (1993), "Neighborhood subtree tolerance charts", Discrete Applied Mathematics , 43 : 13–26, doi : 10.1016 / 0166-218X (93) 90165-K.
- Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaiska grafer och intervalldiagram är bladkrafter ", LATIN 2008: Teoretisk informatik , Föreläsningsanteckningar i beräkning. Sci., 4957 , Springer, Berlin, s. 479–491, doi : 10.1007 / 978-3-540-78773-0_42 , ISBN 978-3-540-78772-3, MR 2472761.
- 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, CiteSeerX 10.1.1.144.3486 , doi : 10.1016 / j.ipl.2006.01 .004.
- Brandstädt, Andreas ; Le, Van Bang; Sritharan, R. (2008), "Structure och linjär tids erkännande av 4-blad befogenheter", ACM Transactions on Algorithms , 5 : 1-22, doi : 10,1145 / 1435375,1435386 , S2CID 6.114.466.
- Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Grafklasser: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6.
- Broin, MW; Lowe, TJ (1986), "Neighborhood subtree tolerance charts", SIAM J. Algebr. Diskreta metoder , 7 : 348–357, doi : 10.1137 / 0607039.
- Dahlhaus, E .; Duchet, P. (1987), "On starkt ackordala grafer", Ars Combinatoria , 24 B : 23–30.
- 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.
- Dom, M .; Guo, J .; Hüffner, F .; Niedermeier, R. (2006), "Fel ersättning blad rot problem", Algorithmica , 44 (4): 363-381, CiteSeerX 10.1.1.218.490 , doi : 10,1007 / s00453-005-1180-z , S2CID 75.279.
- Farber, M. (1983), "Karaktäriseringar av starkt ackorddiagram", Diskret matematik , 43 (2–3): 173–189, doi : 10.1016 / 0012-365X (83) 90154-1.
- Gurski, Frank; Wanke, Egon (2009), "NLC-bredden och klickbredden för kraften i grafer med avgränsad trädbredd", Discrete Applied Mathematics , 157 (4): 583–595, doi : 10.1016 / j.dam.2008.08. 031 , MR 2499471.
- Hayward, RB; Kearney, PE; Malton, A. (2002), "NeST-grafer", Diskret tillämpad matematik , 121 (1–3): 139–153, doi : 10.1016 / s0166-218x (01) 00207-4.
- 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.
- Nishimura, N .; Ragde, P .; Thilikos, DM (2002), "On graf befogenheter för bladmärkta träd", Journal of Algorithms , 42 : 69-108, CiteSeerX 10.1.1.43.1127 , doi : 10,1006 / jagm.2001.1195.
- Rautenbach, D. (2006), "Några anmärkningar om bladrötter", Diskret matematik , 306 (13): 1456–1461, doi : 10.1016 / j.disc.2006.03.030.
- Raychaudhuri, A. (1992), "On powers of starkt ackordala grafer och cirkulära bågediagram", Ars Combinatoria , 34 : 147–160.
- Eppstein, D .; Havvaei, H. (2020), "Parameter Leaf Ström Recognition via inbäddning i graf produkter" , Algorithmica , 82 (8): 2337-2359, doi : 10,1007 / s00453-020-00720-8 , S2CID 218.988.055.