Minimum split coloring
| dc.contributor | Ph.D. Program in Industrial Engineering. | |
| dc.contributor.advisor | Aras, Necati. | |
| dc.contributor.advisor | Ekim Aşıcı, Tınaz. | |
| dc.contributor.author | Yüzsever, Rıdvan Mert. | |
| dc.date.accessioned | 2023-03-16T10:35:21Z | |
| dc.date.available | 2023-03-16T10:35:21Z | |
| dc.date.issued | 2012. | |
| dc.description.abstract | Combinatorial optimization is a very important branch of optimization eld. Many problems in the real world such as transportation, scheduling, production, and telecommunication can be modeled as a combinatorial optimization problem. Although a combinatorial optimization problem has a nite set of solutions, examination of this solution space is not easy to accomplish in many problems. Graph theory is one of the most studied elds in optimization for decades. There is a huge literature on this eld with very di erent approaches. One of the most famous problems in this eld is the graph coloring problem. This is due to the fact that it has a wide range of applications but in the same time, it is extremely di cult to nd an e cient way to solve it. Column generation method embedded in a branch-and-bound tree is a success story in dealing with di cult optimization problems. In most of the cases, it is better than the enumeration of the solution space and dynamic programming solution method in combinatorial optimization problems. In this thesis, we consider a generalization of the graph coloring problem called Minimum Split Coloring Problem which covers an even wider application area. We develop a column generation method embedded in a branch-and-bound tree to solve the Minimum Split Coloring Problem exactly in general graphs. | |
| dc.format.extent | 30 cm. | |
| dc.format.pages | xiii, 84 leaves ; | |
| dc.identifier.other | IE 2012 Y88 PhD | |
| dc.identifier.uri | https://digitalarchive.library.bogazici.edu.tr/handle/123456789/13556 | |
| dc.publisher | Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2012. | |
| dc.relation | Includes appendices. | |
| dc.relation | Includes appendices. | |
| dc.subject.lcsh | Graph coloring. | |
| dc.subject.lcsh | Graph theory. | |
| dc.title | Minimum split coloring |
Files
Original bundle
1 - 1 of 1