Vertex ranking with capacity

G.R.J. Zwaan, van der

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


    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.
    Original languageEnglish
    Title of host publicationSOFSEM 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
    EditorsJ. Leeuwen, van, A. Muscholl, D. Peleg, J. Pokorný, B. Rumpe
    Place of PublicationBerlin
    ISBN (Print)978-3-642-11266-9
    Publication statusPublished - 2010

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'Vertex ranking with capacity'. Together they form a unique fingerprint.

    Cite this