شماره ركورد كنفرانس :
3806
عنوان مقاله :
An Integer Programming for the Coloring Problem of graphs
عنوان به زبان ديگر :
An Integer Programming for the Coloring Problem of graphs
پديدآورندگان :
Ramezani F ramezani@kntu.ac.ir K. N. Toosi University of Technology, Tehran,
عنوان كنفرانس :
دهمين كنفرانس ملي نظريه گراف و تركيبات جبري
چكيده فارسي :
An interval graph is the intersection graph of a set of real intervals. There exist
some handy characterization of them and several graph parameters can be found on
them in polynomial time. Here we present an integer programming for the coloring
problem of graphs and prove that for the interval graphs the optimal solutions of
integer programming and the correspondig LP coincide. Then this gives another
polynomial time algorithm for the coloring problem of interval graphs.
چكيده لاتين :
An interval graph is the intersection graph of a set of real intervals. There exist
some handy characterization of them and several graph parameters can be found on
them in polynomial time. Here we present an integer programming for the coloring
problem of graphs and prove that for the interval graphs the optimal solutions of
integer programming and the correspondig LP coincide. Then this gives another
polynomial time algorithm for the coloring problem of interval graphs.
