If ω(H)=2, then H contains no odd-cycle since height = 3 bipartite graph →χ(H)=2 Given vertex weights, we proposed a simple polynomial time multicoloring algorithm.Ħ 0 6 9 3 3 Theorem Requied # of colors ≦ 4/3×χ(G,w) An approximation algorithm for multicoloring U.D.G. perfect Proof (abstract) H: (vertex) induced subgraph When ω(H)=1 or 3, it is trivial. We propose a polynomial time approximation algorithm based on graph perfectness. An optimal multicoloring of (G,w) is obtained in (strongly) polynomial time.Īn approximation algorithm We find perfect subgraphs. Theorem If graph G is perfect, then ω(G,w)= (G,w), for every w. Multicoloring problem and perfect graph Notation ω(G,w): weighted clique number of (G,w) (G,w): multicoloring number of (G,w) For weighted cases, the following theorem is known. Key property of this talk: graph perfectness.It is important to find well-solvable cases to develop efficient approximation algorithms.We investigate polynomial time approximation algorithms for multicoloring unit disk graphs on triangular lattice points. Weighted unit disk graph on triangular lattice points 3 weight We deal with finite graphs. Triangular lattice points This figure shows triangular lattice points. Multicoloring problem Assigned colors Weight Input:simple undirected graph G=(V,E)vertex weight function w: V →Z+ T dE(v,w): Euclidean distance between the pair v & w We restrict centers of disks to triangular lattice points. Main purpose: Discuss perfectness & imperfectness of unit disk graphs on triangular lattice points Outline Definition Unit disk graph Multicoloring, weighted coloring Triangular lattice points Perfectness & imperfectness Approximation algorithms for multicoloring Maximum weight independent set Imperfection ratio Multicoloring Unit Disk Graphs on Triangular Lattice Points Yuichiro MIYAMOTO Sophia University Tomomi MATSUI University of Tokyo
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |