Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333910 | Theoretical Computer Science | 2011 | 8 Pages |
Abstract
In the paper, we show that the PDTC problem can be solved in polynomial time when the number of stacks s is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring (BC) problem on permutation graphs: for the latter problem, s is the number of colors and h is the number of vertices that can get a same color. We show that the BC problem can be solved in polynomial time when s is a fixed constant on co-comparability graphs, a superclass of permutation graphs. To the contrary, the BC problem is known to be hard on permutation graphs when hâ¥6 is a fixed constant, but s is unbounded.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Flavia Bonomo, Sara Mattia, Gianpaolo Oriolo,