An algorithm for the weighted stable set problem in {claw, net}-free graphs with

详细信息    查看全文

• 作者：Paolo Nobili^a ; Antonio Sassano^b ; ^{sassano@dis.uniroma1.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Claw-free graphs ; Net-free graphs ; Stable set ; Matching
• 刊名：Discrete Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：19
• 期：Complete
• 页码：63-78
• 全文大小：713 K

文摘

In this paper we show that a connected {claw, net}-free graph g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si3.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=c62c1c8669b67f25c945be10b1ff4274" title="Click to view the MathML source">G(V,E)gif" overflow="scroll">G(V,E) with g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si2.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=bd537098bb772c86c264773b90aa2778" title="Click to view the MathML source">α(G)≥4gif" overflow="scroll">α(G)≥4 is the union of a strongly bisimplicial   clique g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si5.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=24325bba14ba82b0fe81865eb2b8193f" title="Click to view the MathML source">Qgif" overflow="scroll">Q and at most two clique-strips  . A clique is strongly bisimplicial if its neighborhood is partitioned into two cliques which are mutually non-adjacent and a clique-strip is a sequence of cliques g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si6.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=a0c139ddf4a2e60252cb76263f431738" title="Click to view the MathML source">{H₀,…,H_p}gif" overflow="scroll">{H0,…,Hp} with the property that g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si7.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=fe397151382c1a7ff54ff0fd2a087a77" title="Click to view the MathML source">H_igif" overflow="scroll">Hi is adjacent only to g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si8.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=34c130e81ee43cb09a21fc5e620aeed8" title="Click to view the MathML source">H_i−1gif" overflow="scroll">Hi−1 and g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si9.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=db53487e4b0006d197d6e9081ad1a216" title="Click to view the MathML source">H_i+1gif" overflow="scroll">Hi+1. By exploiting such a structure we show how to solve the Maximum Weight Stable Set Problem   in such a graph in time g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si10.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=9b692073553801c081182018b1662560">g class="imgLazyJSB inlineImage" height="15" width="72" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S1572528616000037-si10.gif">gif" overflow="scroll">O(|V||E|), improving the previous complexity bound of g" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000037&_mathId=si11.gif&_user=111111111&_pii=S1572528616000037&_rdoc=1&_issn=15725286&md5=def4b167bc3ddf7ea58c40f1d68f9e86" title="Click to view the MathML source">O(|V||E|)gif" overflow="scroll">O(|V||E|).