http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : Strømme, Torstein J.F. (검색결과 1 건)
- 무료
- 기관 내 무료
- 유료
-
A width parameter useful for chordal and co-comparability graphs
Kang, Dong Yeap,Kwon, O-joung,Strømme, Torstein J.F.,Telle, Jan Arne Elsevier 2017 Theoretical computer science Vol.704 No.-
<P><B>Abstract</B></P> <P>Belmonte and Vatshelle (TCS 2013) used mim-width, a graph width parameter bounded on interval graphs and permutation graphs, to explain existing algorithms for many domination-type problems on those graph classes. We investigate new graph classes of bounded mim-width, strictly extending interval graphs and permutation graphs. The graphs <SUB> K t </SUB> ⊟ <SUB> K t </SUB> and <SUB> K t </SUB> ⊟ <SUB> S t </SUB> are graphs obtained from the disjoint union of two cliques of size <I>t</I>, and one clique of size <I>t</I> and one independent set of size <I>t</I> respectively, by adding a perfect matching. We prove that:<UL> <LI> interval graphs are ( <SUB> K 3 </SUB> ⊟ <SUB> S 3 </SUB> ) -free chordal graphs; and ( <SUB> K t </SUB> ⊟ <SUB> S t </SUB> ) -free chordal graphs have mim-width at most t − 1 , </LI> <LI> permutation graphs are ( <SUB> K 3 </SUB> ⊟ <SUB> K 3 </SUB> ) -free co-comparability graphs; and ( <SUB> K t </SUB> ⊟ <SUB> K t </SUB> ) -free co-comparability graphs have mim-width at most t − 1 , </LI> <LI> chordal graphs and co-comparability graphs have unbounded mim-width in general. </LI> </UL> We obtain several algorithmic consequences; for instance, while <SMALL>MINIMUM DOMINATING SET</SMALL> is NP-complete on chordal graphs, it can be solved in time <SUP> n O ( t ) </SUP> on ( <SUB> K t </SUB> ⊟ <SUB> S t </SUB> ) -free chordal graphs. The third statement strengthens a result of Belmonte and Vatshelle stating that either those classes do not have constant mim-width or a decomposition with constant mim-width cannot be computed in polynomial time unless P = N P .</P> <P>We generalize these ideas to bigger graph classes. We introduce a new width parameter <I>sim-width</I>, of stronger modeling power than mim-width, by making a small change in the definition of mim-width. We prove that chordal graphs and co-comparability graphs have sim-width at most 1. We investigate a way to bound mim-width for graphs of bounded sim-width by excluding <SUB> K t </SUB> ⊟ <SUB> K t </SUB> and <SUB> K t </SUB> ⊟ <SUB> S t </SUB> as induced minors or induced subgraphs, and give algorithmic consequences. Lastly, we show that circle graphs have unbounded sim-width, and thus also unbounded mim-width.</P>
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
