MARC보기
LDR00000nmm u2200205 4500
001000000331613
00520241119162825
008181129s2018 ||| | | | eng d
020 ▼a 9780438350403
035 ▼a (MiAaPQ)AAI10931440
035 ▼a (MiAaPQ)columbia:14867
040 ▼a MiAaPQ ▼c MiAaPQ ▼d 248032
0491 ▼f DP
0820 ▼a 658
1001 ▼a Zhong, Mingxian.
24510 ▼a Some Problems in Graph Theory and Scheduling.
260 ▼a [S.l.] : ▼b Columbia University., ▼c 2018
260 1 ▼a Ann Arbor : ▼b ProQuest Dissertations & Theses, ▼c 2018
300 ▼a 126 p.
500 ▼a Source: Dissertation Abstracts International, Volume: 80-02(E), Section: B.
500 ▼a Adviser: Clifford Stein.
5021 ▼a Thesis (Ph.D.)--Columbia University, 2018.
520 ▼a In this dissertation, we present three results related to combinatorial algorithms in graph theory and scheduling, both of which are important subjects in the area of discrete mathematics and theoretical computer science. In graph theory, a grap
520 ▼a The first two results are related to coloring graphs belonging to specific classes. In scheduling problems, we are interested in how to efficiently schedule a set of jobs on machines. The last result is related to a scheduling problem in an envi
520 ▼a A graph is H-free if it has no induced subgraph isomorphic to H. In the second part of this thesis, we characterize all graphs H for which there are only finitely many minimal non-three-colorable H-free graphs. This solves a problem posed by G
520 ▼a The last result of this thesis deals with a scheduling problem addressing the uncertainty regarding the machines. We study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and
590 ▼a School code: 0054.
650 4 ▼a Operations research.
650 4 ▼a Computer science.
650 4 ▼a Mathematics.
690 ▼a 0796
690 ▼a 0984
690 ▼a 0405
71020 ▼a Columbia University. ▼b Operations Research.
7730 ▼t Dissertation Abstracts International ▼g 80-02B(E).
773 ▼t Dissertation Abstract International
790 ▼a 0054
791 ▼a Ph.D.
792 ▼a 2018
793 ▼a English
85640 ▼u http://www.riss.kr/pdu/ddodLink.do?id=T15001035 ▼n KERIS
980 ▼a 201812 ▼f 2019
990 ▼a 관리자 ▼b 관리자