A cost of a path may not be the only factor in searching for a path solution in a network. For example, some applications are delay sensitive and require finding a path that does not exceed a latency constraint for the entire path. Accordingly, a method and corresponding apparatus for searching for a path solution in a network is provided that identifies combinations of partial paths that satisfy an end-to-end path constraint, compares attributes of the combinations of partial paths, prunes the combinations of partial paths based on results of the comparing to identify candidate combinations of partial paths, and selects a candidate combination of partial paths as the path solution. By pruning combinations of partial paths, considerable is saved compared to exhaustive comparing of every possible combination of partial paths and scalability is achieved.