The Central Bag Method: An Approach to Analyzing the Structure of Hereditary Graph Classes- [electronic resource]
The Central Bag Method: An Approach to Analyzing the Structure of Hereditary Graph Classes- [electronic resource]
- 자료유형
- 학위논문파일 국외
- 최종처리일시
- 20240214101515
- ISBN
- 9798380415552
- DDC
- 510
- 저자명
- Abrishami, Tara.
- 서명/저자
- The Central Bag Method: An Approach to Analyzing the Structure of Hereditary Graph Classes - [electronic resource]
- 발행사항
- [S.l.]: : Princeton University., 2023
- 발행사항
- Ann Arbor : : ProQuest Dissertations & Theses,, 2023
- 형태사항
- 1 online resource(123 p.)
- 주기사항
- Source: Dissertations Abstracts International, Volume: 85-03, Section: A.
- 주기사항
- Advisor: Chudnovsky, Maria.
- 학위논문주기
- Thesis (Ph.D.)--Princeton University, 2023.
- 사용제한주기
- This item must not be sold to any third party vendors.
- 초록/해제
- 요약In this thesis we develop the central bag method. The central bag method uses the structure of cutsets in a graph G to construct an induced subgraph β of G with two key features: 1. Every component of G \\ β has small weight and has constant-size neighborhood in β ; and 2. the properties of β are "nicer'" than the properties of G . The central bag was inspired by properties of tree decompositions and is analogous to a single bag of a well-chosen tree decomposition of G . The main application of the central bag method is to prove that hereditary graph classes have bounded treewidth. In this thesis, we show how the central bag method can be used to prove that (theta, pyramid, prism, line wheel, Kt)-free graphs have logarithmic treewidth (in the number of vertices), that (even hole, pyramid, diamond, Kt)-free graphs have constant treewidth, and that (propeller, Wt*t, Kt)-free graphs have constant treewidth. The central bag method has also been used to prove that the MAXIMUM WEIGHT INDEPENDENT SET problem (MWIS) is polynomial-time solvable in certain hereditary graph classes. In this thesis, we show how the central bag method can be used to prove that MWIS is polynomial-time solvable in a subclass of perfect graphs and in (Sttt, Kt, Ktt)-free graphs.
- 일반주제명
- Mathematics.
- 일반주제명
- Theoretical mathematics.
- 일반주제명
- Mathematics education.
- 키워드
- Graph theory
- 키워드
- Treewidth
- 기타저자
- Princeton University Applied and Computational Mathematics
- 기본자료저록
- Dissertations Abstracts International. 85-03A.
- 기본자료저록
- Dissertation Abstract International
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.