抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1600000, indirect: 480000)
We have developed fixed-parameter algorithms or proved the hardness of vertex coloring problems on parameterized graphs obtained by adding or deleting edges from graphs in classes such as comparability graphs, permutation graphs and grid graphs. We have also developed a fixed-parameter algorithm for isomorphism of tree+ ke graphs. In addition, we have clarified the property of problems and parameterized graph classes which makes it possible to design fixed-parameter algorithms.