Problemet med Subgraph Isomorphism definieras enligt följande: Med tanke på ett mönster H och en värdgraf G på n hörn, innehåller G en subgraf som är isomorphic till H? Eppstein [SODA 95, J'GAA 99] ger den första linjära tid algoritm för subgraph isomorfism för en fast storlek mönster, till exempel ordning k, och godtycklig planar värdgraf, förbättra på O(n Eppstein algoritm körs i tid k O(k) n, det vill säga beroendet av k är superexponentiell. Vi löser ett öppet problem som finns i Eppsteins papper och förbättrar körtiden till 2 O(k) n, det vill säga enstaka exponentiella i k samtidigt som termen hålls i n linjär. Bredvid att bestämma subgraph isomorfism, kan vi konstruera en lösning och räkna alla lösningar i samma asymptotic körtid. Vi kan räkna upp subgrafer med en additiv term O(enk) i körtiden för vår algoritm. Vi introducerar tekniken för "inbäddad dynamisk programmering" på en lämpligt strukturerad graf sönderdelning, som utnyttjar topologin av de underliggande inbäddningar av subgrafen mönster (snarare än värdgrafen). För att uppnå våra resultat ger vi en övre gräns för antalet partiella lösningar i varje dynamiskt programmeringssteg som en funktion av mönsterstorlek-som det visar sig, för planar subgraph isomorfism problem, att funktionen är enstaka exponentiellt i antalet hörn i mönstret.
Dorn REF skärpte senare körtiden till 2 O(k) n genom att utnyttja planaritet i den dynamiska programmeringsdelrutinen.
Planar Subgraph Isomorphism Revisited
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}