Efficient Algorithms for Partitionings, Colorings and Drawings of Graphs and their Applications

点击翻译按钮获取中文摘要

This research develops efficient algorithms for the partitioning, coloring and drawing problems of graphs, and applies them to practical problems in real world. One of the representative results is an algorithm for the fairest connected partition problem. It partitions a weighted graph G to a specified number of connected subgraphs by deleting edges from G so that the difference between the maximum sum of weights in a subgraph and the minimum one is as small as possible.