algorithm - How to solve Subtree Isomorphism using maximum bipartite matching? -


how determine if given tree t contains subtree isomorphic tree s?

two trees called isomorphic if 1 of them can obtained other series of flips, i.e. swapping left , right children of number of nodes. number of nodes @ level can have children swapped. 2 empty trees isomorphic.

i've read @ few places bipartiate matching algorithms can used solve problem can't find non-paywalled sources details. there seems many research papers on problem, of them again behind paywall, i'm not interested in latest research algorithm problem. question how bipartiate matching applies problem?

ps: there seems confusion on internet meant "isomorphic". above definition found @ places places mentioned "isomorphic" means trees of same shape regardless of node values. if can clear confusion, had great too.

i'm going talk rooted subtree isomorphism; unrooted case can handled without regard efficiency trying roots.

the basic idea if have trees

               b    /|\          /|\   / | \        / | \  /  |  \      /  |  \ a1 ...    b1 ...  bn /\      /\   /\      /\

and want know whether a subtree of b in such way a maps b, i , j, compute recursively whether subtree rooted @ ai subtree of tree rooted @ bj in such way ai maps bj. (the base cases when a or b leaf.) now, it's not enough each subtree mappable, because if bj has particularly rich structure, several ais might subtrees, requirements of isomorphism won't let them share bj. maximum matching comes in: try match of ais bjs in such way subtrees can mapped.

to general rooted problem, try possible choices of b.


Comments

Post a Comment

Popular posts from this blog

jquery - How do you format the date used in the popover widget title of FullCalendar? -

Image
in fullcalendar, how format date used in popover widget title when clicking '+n more'? code: <div class="fc-popover fc-more-popover"> <div class="fc-header fc-widget-header"> <span class="fc-close fc-icon fc-icon-x"></span> <span class="fc-title">tuesday, april 7</span> ... </div> ... </div> you use daypopoverformat that. determines date format of title of popover created eventlimitclick option. must date formatting string. default value "dddd, mmmm d" english , "ll" other languages.
Read more

asp.net mvc - SSO between MVCForum and Umbraco7 -

i need integrate sso between mvcforum (forum of company) , umbraco7 (manages cms company). however struggling shared authentication work. tried several ways suggested on other threads still not running expected. here did: 1. in mvcforum (forum.mywebsite.com) 1.1. machine key in web.xml: <machinekey validationkey="the same key umbraco7" decryptionkey="the same key umbraco7" validation="sha1" decryption="aes" /> 1.2. authenticate forms in web.xml <forms name="my-sso-auth" protection="all" path="/" timeout="43200" domain="forum.mywebsite.com" loginurl="/members/logon" enablecrossappredirects="true" /> 2. in umbraco7 (news.mywebsite.com) 2.1. machine key in web.xml: <machinekey validationkey="the same key mvcforum" decryptionkey="the same key mvcforum" validation="sha1" decryption="aes" /> 2.2. a...
Read more

Python Tkinter keyboard using bind -

i have problem using bind option can click button in keyboard, , call function once key pressed. tried taking other codes have similar purpose , saw i'm doing pretty same, though still have problem must've missed. thankful if me this. here's code: # -*- coding: utf-8 -*- #imports tkinter import * pil import imagetk, image import time import tkmessagebox #===========================================================================================================================================# #tkinter class class app(frame): def __init__(self, master=none): frame.__init__(self, master) self.pack() #===========================================================================================================================================# #game pieces classes class board: def __init__(self, rows = 7, columns = 6, picture_height = none, picture_width = none): self.rows = rows self.columns = columns self.picture ...
Read more