
induced matching

graph sidhaanthathil, oru dishaabodhamillaatha graafinte arikukalude oru upavibhagamaanu induced matching allengil sakthamaaya matching, athu oru shringavum pankidunnilla (ithu oru poruthamaanu) koodaathe upavibhaagathile eathenkilum rund konukale bandhippikkunna oro arikum ulppedunnu (ithu oru induced subgraph aanu).
thannirikkunna graafinte line graafinte chathuratthile oru swatantra ganamayum induced matching visheshippikkaam.
sakthamaaya niravum ayalpakkangalum.
oru graafinte arikukal vibhajikkaan kazhiyunna ettavum kuranja induced poruthangalude ennathe athinte "sakthamaaya chrometic soochika" ennu vilikkunnu, graafinte chrometic soochikayumaayi saamyam vachaal, athinte arikukal vibhajikkaan kazhiyunna ettavum kuranja poruthangalude ennamaanu. ithu line graafinte chathuratthinte chrometic samkhyaykku thulyamaanu. line graafinte chathuratthil prayogikkunna brooks sidhaantham,
thannirikkunna graafinte paramavadhi digriyil sakthamaaya chrometic soochika ettavum chathuraakrithiyilaannennu kaanikkunnu, ennaal chathuraakrithiyilulla bandhatthile mikacha sthira gadakangal mattu reethikaliloode nedaanaakum.
rusa-semeready prashnam rekheeya sakthamaaya chrometic soochikayulla santhulithamaaya bipartite graafukalude edju densityumaayi bandhappettirikkunnu. thulyamaayi, ithu vyathyastha klaas graafukalude saandrathayekkurichaanu, praadeshikamaayi leanier graafukalil oro sheershakathinteyum ayalpakkathu oru induced matching aanu. itharathilulla graafukalkkonnum chathuraakrithiyilulla arikukal undaakilla, ennaal ekadesham chathuraakrithiyilulla arikukalulla itharathilulla graafukalkku nirmmanangal ariyappedunnu.
computational sankeernnatha.
kuranjathu formula _ 1-nte valuppathinte oru induced matching kandethunnathu enpi-complete aanu (athinaal, paramavadhi valuppathinte induced matching kandethunnathu enpi-haard aanu). cordell graafukalil polynomial samayat ithu pariharikkan kazhiyum, kaaranam cordell graafukalude line graafukalude squareukal thikanja graafukalaanu.
koodaathe, ithu cordell graafukalil leanier samayat pariharikkan kazhiyum.
bahupada shreniyil apratheekshithamaya oru thakarcha sambhavikkunnillenkil,
ettavum valia induced matching polynomial samayathile oru soothravaakyathilum _ 2 ekadesha anupaathathil kanakkakkaan kazhiyilla.
prashnam dablyu [1]-haard aanu, athaayath oru nischitha valuppa formulayude oru cheria induced matching kandethuka polum ellah formulakalum _ 1-tappilukal arikukal pareekshikkunathinulla broot fozhsu serch sameepanathekkaal ganyamaayi vegathil oru algoritam undakaan saadhyathayilla. ennirunnaalum, neekkam cheiyunnathiloode oru induced matching avasheshikkunna formula _ 1 vertisukal kandethunnathile prashnam fixed-paaraameettar tractable aanu. exponential space ulla time formula 7-leeii formula _ 6-vertex graafukalilo polynomial space ulla time formula _ 8-lum prashnam krithyamaayi pariharikkanaakum.

