語系:
繁體中文
English
說明(常見問題)
回圖書館首頁
手機版館藏查詢
登入
回首頁
切換:
標籤
|
MARC模式
|
ISBD
On Recognition Algorithms and Struct...
~
Cook, Linda J.
FindBook
Google Book
Amazon
博客來
On Recognition Algorithms and Structure of Graphs with Restricted Induced Cycles.
紀錄類型:
書目-電子資源 : Monograph/item
正題名/作者:
On Recognition Algorithms and Structure of Graphs with Restricted Induced Cycles./
作者:
Cook, Linda J.
出版者:
Ann Arbor : ProQuest Dissertations & Theses, : 2021,
面頁冊數:
112 p.
附註:
Source: Dissertations Abstracts International, Volume: 82-12, Section: B.
Contained By:
Dissertations Abstracts International82-12B.
標題:
Mathematics. -
電子資源:
https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28498115
ISBN:
9798515256609
On Recognition Algorithms and Structure of Graphs with Restricted Induced Cycles.
Cook, Linda J.
On Recognition Algorithms and Structure of Graphs with Restricted Induced Cycles.
- Ann Arbor : ProQuest Dissertations & Theses, 2021 - 112 p.
Source: Dissertations Abstracts International, Volume: 82-12, Section: B.
Thesis (Ph.D.)--Princeton University, 2021.
This item must not be sold to any third party vendors.
We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length.Forbidding holes of certain types in a graph has deep structural implications.In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole.In 2002, Conforti, Cornuejols, Kapoor and Vuskovic provided a structural description of the class of even-hole-free graphs. In Chapter 3, we provide a structural description of all graphs that contain only holes of length ℓ for every ℓ ≥ 4.Analysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities.In 1991, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex v∈V(G). In 2002, Conforti, Cornuejols, Kapoor and Vuskovic gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003, Chudnovsky, Kawarabayashi and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019, Chudnovsky, Scott, Seymour and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year, Chudnovsky, Scott and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least ℓ for any fixed integer ℓ ≥ 5. In Chapter 2, we provide a polynomial-time algorithm to test whether a graph contains an even hole of length at least ℓ for any fixed integer ℓ ≥ 4.
ISBN: 9798515256609Subjects--Topical Terms:
515831
Mathematics.
Subjects--Index Terms:
Graph Theory
On Recognition Algorithms and Structure of Graphs with Restricted Induced Cycles.
LDR
:02876nmm a2200397 4500
001
2282964
005
20211022115811.5
008
220723s2021 ||||||||||||||||| ||eng d
020
$a
9798515256609
035
$a
(MiAaPQ)AAI28498115
035
$a
AAI28498115
040
$a
MiAaPQ
$c
MiAaPQ
100
1
$a
Cook, Linda J.
$3
3561850
245
1 0
$a
On Recognition Algorithms and Structure of Graphs with Restricted Induced Cycles.
260
1
$a
Ann Arbor :
$b
ProQuest Dissertations & Theses,
$c
2021
300
$a
112 p.
500
$a
Source: Dissertations Abstracts International, Volume: 82-12, Section: B.
500
$a
Advisor: Seymour, Paul.
502
$a
Thesis (Ph.D.)--Princeton University, 2021.
506
$a
This item must not be sold to any third party vendors.
520
$a
We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length.Forbidding holes of certain types in a graph has deep structural implications.In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole.In 2002, Conforti, Cornuejols, Kapoor and Vuskovic provided a structural description of the class of even-hole-free graphs. In Chapter 3, we provide a structural description of all graphs that contain only holes of length ℓ for every ℓ ≥ 4.Analysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities.In 1991, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex v∈V(G). In 2002, Conforti, Cornuejols, Kapoor and Vuskovic gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003, Chudnovsky, Kawarabayashi and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019, Chudnovsky, Scott, Seymour and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year, Chudnovsky, Scott and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least ℓ for any fixed integer ℓ ≥ 5. In Chapter 2, we provide a polynomial-time algorithm to test whether a graph contains an even hole of length at least ℓ for any fixed integer ℓ ≥ 4.
590
$a
School code: 0181.
650
4
$a
Mathematics.
$3
515831
650
4
$a
Computer science.
$3
523869
650
4
$a
Applied mathematics.
$3
2122814
653
$a
Graph Theory
653
$a
Holes
653
$a
Induced subgraph
653
$a
Long even hole
653
$a
Monoholed graph
653
$a
Structural graph theory
653
$a
Recognition algorithms
690
$a
0405
690
$a
0984
690
$a
0364
710
2
$a
Princeton University.
$b
Applied and Computational Mathematics.
$3
3182352
773
0
$t
Dissertations Abstracts International
$g
82-12B.
790
$a
0181
791
$a
Ph.D.
792
$a
2021
793
$a
English
856
4 0
$u
https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28498115
筆 0 讀者評論
館藏地:
全部
電子資源
出版年:
卷號:
館藏
1 筆 • 頁數 1 •
1
條碼號
典藏地名稱
館藏流通類別
資料類型
索書號
使用類型
借閱狀態
預約狀態
備註欄
附件
W9434697
電子資源
11.線上閱覽_V
電子書
EB
一般使用(Normal)
在架
0
1 筆 • 頁數 1 •
1
多媒體
評論
新增評論
分享你的心得
Export
取書館
處理中
...
變更密碼
登入