Vertex ranking has many practical applications, ranging from VLSI layout and sparse matrix factorization to parallel query processing and assembly of modular products.
Much research has been done on vertex ranking and related problems, polynomial time algorithms are known for a wide variety of graph classes as well as NP-hardness has been shown for other graph classes. In this paper we propose an extension to vertex ranking. Vertex ranking has many applications in computing a parallel schedule, but there is the assumption that the amount of parallel capacity is unbounded. Many applications do have restricted capacity, such as the number of processors or machines. Therefore we introduce vertex ranking with capacity.
In this paper we show that vertex ranking and vertex ranking with capacity do not have a polynomial sized kernel, unless all coNP-complete problems have distillation algorithms. Having to deal with the NP- hardness of both problems, we give, to our knowledge, the first O *(2 n ) time exact algorithm for vertex ranking and use this for devising an O *(2.5875 n ) time algorithm for vertex ranking with capacity. We also show that we can transform vertex rankings to vertex rankings with capacity, and use this for a polynomial time algorithm that transforms an f(n)-approximate vertex ranking to a vertex ranking with capacity of at most f(n)¿+¿1 times the optimum size. Lastly, give an log(c) additive approximation for vertex ranking with capacity when restricted to trees and extend this to graphs of bounded treewidth.
|Title of host publication||SOFSEM 2010: Theory and Practice of Computer Science : 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings|
|Editors||J. Leeuwen, van, A. Muscholl, D. Peleg, J. Pokorný, B. Rumpe|
|Place of Publication||Berlin|
|Publication status||Published - 2010|
|Name||Lecture Notes in Computer Science|