ONLINE COLORING CO-INTERVAL GRAPHS

Q: How can I download an article?

To download an article from SID, first log in to the site, search for the article title, and click on the 'Download Article' option.

Q: How can I download an ISI article?

To download an ISI article on SID, enter the keyword or article title in the search bar, view the relevant results, click on the desired article, and select the 'Download Article' option.

Q: How can I access the SID database?

To access the SID database, visit SID.ir, create an account, and log in to access scientific resources.

Q: Is downloading articles from SID free?

Some articles on SID are available for free, while others require payment. Details are specified on the article's page.

ZARABIZADEH H.

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Journal Paper

Paper Information

Journal: Scientia Iranica Year:2009 | Volume:16 | Issue:1 ( TRANSACTIONS D: COMPUTER SCIENCE AND ENGINEERING) Page(s): 1-7

Download Full-Text

View:

359

Download:

164

Cites:

Information Journal Paper

Title

ONLINE COLORING CO-INTERVAL GRAPHS

Author(s)

ZARABIZADEH H. | Issue Writer Certificate

Keywords

ONLINE ALGORITHMS; GRAPH COLORING; CO-INTERVAL GRAPHS

Abstract

We study the problem of online coloring co-interval graphs. In this problem, a set of intervals on the real line is presented to the algorithm, one at a time, and upon receiving each interval I, the algorithm must assign I a color different from the colors of all previously presented intervals not intersecting I. The objective is to use as few colors as possible. It is known that the competitive ratio of the simple FIRST-FIT algorithm on the class of co-interval graphs is at most 2. We show that for the class of unit co-interval graphs, where all intervals have equal length, the 2-bound on the competitive ratio of FIRST-FIT is tight. On the other hand, we show that no deterministic online algorithm for coloring unit co-interval graphs can be better than 3/2-competitive. We then study the effect of randomization on our problem and show a lower bound of 4/3 on the competitive ratio of any randomized algorithm for the unit co-interval coloring problem. We also prove that for the class of general co-interval graphs, no randomized algorithm has a competitive ratio better than 3/2.

Multimedia

No record.

Cites

No record.

References

No record.

Cite

APA: Copy

ZARABIZADEH, H.. (2009). ONLINE COLORING CO-INTERVAL GRAPHS. SCIENTIA IRANICA, 16(1 ( TRANSACTIONS D: COMPUTER SCIENCE AND ENGINEERING)), 1-7. SID. https://sid.ir/paper/289816/en

Vancouver: Copy

ZARABIZADEH H.. ONLINE COLORING CO-INTERVAL GRAPHS. SCIENTIA IRANICA[Internet]. 2009;16(1 ( TRANSACTIONS D: COMPUTER SCIENCE AND ENGINEERING)):1-7. Available from: https://sid.ir/paper/289816/en

IEEE: Copy

H. ZARABIZADEH, “ONLINE COLORING CO-INTERVAL GRAPHS,” SCIENTIA IRANICA, vol. 16, no. 1 ( TRANSACTIONS D: COMPUTER SCIENCE AND ENGINEERING), pp. 1–7, 2009, [Online]. Available: https://sid.ir/paper/289816/en

Related Journal Papers

No record.

Related Seminar Papers

No record.

Related Plans

No record.

Recommended Workshops