{"docId":603,"paperId":603,"url":"https:\/\/dmtcs.episciences.org\/603","doi":"10.46298\/dmtcs.603","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":99,"name":"Vol. 15 no. 2"}],"section":[{"sid":16,"title":"Graph and Algorithms","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-00980767","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00980767v1","dateSubmitted":"2009-05-21 00:00:00","dateAccepted":"2015-06-09 14:48:39","datePublished":"2013-08-22 00:00:00","titles":{"en":"On-line ranking of split graphs"},"authors":["Borowiecki, Piotr","Dereniowski, Dariusz"],"abstracts":{"0":"Graphs and Algorithms","en":"A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm and the number of colors used in an optimal off-line solution may be arbitrarily large. This negative result motivates us to investigate semi on-line algorithms, where a split graph is presented on-line but its clique number is given in advance. We prove that there does not exist a (2-\u025b)-competitive semi on-line algorithm of this type. Finally, a 2-competitive semi on-line algorithm is given."},"keywords":["[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}