http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : Sæther, Sigve Hortemo (검색결과 1 건)
- 무료
- 기관 내 무료
- 유료
-
Maximum matching width: New characterizations and a fast algorithm for dominating set
Jeong, Jisu,Sæther, Sigve Hortemo,Telle, Jan Arne Elsevier 2018 Discrete applied mathematics Vol.248 No.-
<P><B>Abstract</B></P> <P>A graph of treewidth k has a representation by subtrees of a ternary tree, with subtrees of adjacent vertices sharing a tree node, and any tree node sharing at most k + 1 subtrees. Likewise for branchwidth, but with a shift to the edges of the tree rather than the nodes. In this paper we show that the mm-width of a graph – maximum matching width – combines aspects of both these representations, targeting tree nodes for adjacency and tree edges for the parameter value. The proof of this new characterization of mm-width is based on a definition of canonical minimum vertex covers of bipartite graphs. We show that these behave in a monotone way along branch decompositions over the vertex set of a graph.</P> <P>We use these representations to compare mm-width with treewidth and branchwidth, and also to give another new characterization of mm-width, by subgraphs of chordal graphs. We prove that given a graph G and a branch decomposition of maximum matching width k we can solve the Minimum Dominating Set Problem in time <SUP> O ∗ </SUP> ( <SUP> 8 k </SUP> ) , thereby beating <SUP> O ∗ </SUP> ( <SUP> 3 tw ( G ) </SUP> ) whenever tw ( G ) > <SUB> log 3 </SUB> 8 × k ≈ 1 . 893 k . Note that mmw ( G ) ≤ tw ( G ) + 1 ≤ 3 mmw ( G ) and these inequalities are tight. Given only the graph G and using the best known algorithms to find decompositions, maximum matching width will be better for Minimum Dominating Set whenever tw ( G ) > 1 . 549 × mmw ( G ) .</P>
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
