東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Graphs of bounded rank-width.

Oum, Sang-Il.

Linked to FindBook

Google Book

Amazon

博客來

Graphs of bounded rank-width.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Graphs of bounded rank-width./
Author:	Oum, Sang-Il.
Description:	155 p.
Notes:	Source: Dissertation Abstracts International, Volume: 66-02, Section: B, page: 0975.
Contained By:	Dissertation Abstracts International66-02B.
Subject:	Applied Mechanics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3164969
ISBN:	0542001314

Graphs of bounded rank-width.
Oum, Sang-Il.

Graphs of bounded rank-width. - 155 p.

Source: Dissertation Abstracts International, Volume: 66-02, Section: B, page: 0975.

Thesis (Ph.D.)--Princeton University, 2005.

We define rank-width of graphs to investigate clique-width. Rank-width is a complexity measure of decomposing a graph in a kind of tree-structure, called a rank-decomposition. We show that graphs have bounded rank-width if and only if they have bounded clique-width.

ISBN: 0542001314Subjects--Topical Terms:

1018410
Applied Mechanics.

Graphs of bounded rank-width.
LDR:02903nmm 2200337 4500 001 1849141
005 20051209075321.5
008 130614s2005 eng d
020 $a 0542001314
035 $a (UnM)AAI3164969
035 $a AAI3164969
040 $a UnM $c UnM
100 1 $a Oum, Sang-Il. $3 1937117
245 1 0 $a Graphs of bounded rank-width.
300 $a 155 p.
500 $a Source: Dissertation Abstracts International, Volume: 66-02, Section: B, page: 0975.
500 $a Adviser: Paul Seymour.
502 $a Thesis (Ph.D.)--Princeton University, 2005.
520 $a We define rank-width of graphs to investigate clique-width. Rank-width is a complexity measure of decomposing a graph in a kind of tree-structure, called a rank-decomposition. We show that graphs have bounded rank-width if and only if they have bounded clique-width.
520 $a It is unknown how to recognize graphs of clique-width at most k for fixed k > 3 in polynomial time. However, we find an algorithm recognizing graphs of rank-width at most k, by combining following three ingredients.
520 $a First, we construct a polynomial-time algorithm, for fixed k , that confirms rank-width is larger than k or outputs a rank-decomposition of width at most f (k) for some function f. It was known that many hard graph problems have polynomial-time algorithms for graphs of bounded clique-width, however, requiring a given decomposition corresponding to clique-width (k-expression ); we remove this requirement.
520 $a Second, we define graph vertex-minors which generalizes matroid minors, and prove that if {G1, G2,...} is an infinite sequence of graphs of bounded rank-width, then there exist i < j such that Gi is isomorphic to a vertex-minor of Gj. Consequently there is a finite list Ck of graphs such that a graph has rank-width at most k if and only if none of its vertex-minors are isomorphic to a graph in Ck .
520 $a Finally we construct, for fixed graph H, a modulo-2 counting monadic second-order logic formula expressing a graph contains a vertex-minor isomorphic to H. It is known that such logic formulas are solvable in linear time on graphs of bounded clique-width if the k-expression is given as an input.
520 $a Another open problem in the area of clique-width is Seese's conjecture; if a set of graphs have an algorithm to answer whether a given monadic second-order logic formula is true for all graphs in the set, then it has bounded rank-width. We prove a weaker statement; if the algorithm answers for all modulo-2 counting monadic second-order logic formulas, then the set has bounded rank-width.
590 $a School code: 0181.
650 4 $a Applied Mechanics. $3 1018410
650 4 $a Computer Science. $3 626642
690 $a 0346
690 $a 0984
710 2 0 $a Princeton University. $3 645579
773 0 $t Dissertation Abstracts International $g 66-02B.
790 1 0 $a Seymour, Paul, $e advisor
790 $a 0181
791 $a Ph.D.
792 $a 2005
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3164969