umu.sePublications

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt152",{id:"formSmash:upper:j_idt152",widgetVar:"widget_formSmash_upper_j_idt152",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt153_j_idt155",{id:"formSmash:upper:j_idt153:j_idt155",widgetVar:"widget_formSmash_upper_j_idt153_j_idt155",target:"formSmash:upper:j_idt153:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Simulation relations for pattern matching in directed graphsPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
2013 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 485, p. 1-15Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2013. Vol. 485, p. 1-15
##### Keywords [en]

Pattern matching, Simulation, Graphs, Treebanks, Complexity, simulation relations
##### National Category

Mathematics
##### Identifiers

URN: urn:nbn:se:umu:diva-76270DOI: 10.1016/j.tcs.2013.03.021ISI: 000319487500001OAI: oai:DiVA.org:umu-76270DiVA, id: diva2:635966
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt451",{id:"formSmash:j_idt451",widgetVar:"widget_formSmash_j_idt451",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt457",{id:"formSmash:j_idt457",widgetVar:"widget_formSmash_j_idt457",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt463",{id:"formSmash:j_idt463",widgetVar:"widget_formSmash_j_idt463",multiple:true}); Available from: 2013-07-08 Created: 2013-07-08 Last updated: 2018-06-08Bibliographically approved

We consider the problem of finding the occurrences of a pattern tree t in a directed graph g, and propose two algorithms, one for preprocessing and one for searching for t in g. It is assumed that the object graph itself is large and static, and that the pattern tree is small and frequently updated. To model varying abstraction levels in the data, we work with partially ordered alphabets and compute simulation relations rather than equivalence relations. In particular, vertices and edges are labelled with elements from a pair of preorders instead of unstructured alphabets. Under the above assumptions, we obtain a search algorithm that runs in time O(height (t) . vertical bar t vertical bar . vertical bar(V-g(+/-)t/R-g(+/-)t vertical bar(2)) where vertical bar (V-g(+/-)t/R-g(+/-)t)vertical bar is the number of equivalence classes in the coarsest simulation relation R-g(+/-)t on the graph g((+/-))t, the disjoint union of g and t. This means that the size of the object graph only affects the running time of the search algorithm indirectly, because of the groundwork done by the preprocessing routine in time O(k . vertical bar g vertical bar . vertical bar(V-g/R-g)vertical bar(2)), where vertical bar(V-g/R-g) is the number of equivalence classes in the coarsest simulation relation R-g on g, taking k = vertical bar V-g vertical bar(2) in the general case and k = height (g) if g is acyclic.

doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1180",{id:"formSmash:j_idt1180",widgetVar:"widget_formSmash_j_idt1180",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1234",{id:"formSmash:lower:j_idt1234",widgetVar:"widget_formSmash_lower_j_idt1234",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1235_j_idt1237",{id:"formSmash:lower:j_idt1235:j_idt1237",widgetVar:"widget_formSmash_lower_j_idt1235_j_idt1237",target:"formSmash:lower:j_idt1235:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});