Journal of Graph Algorithms and Applications