Exploiting the computational power of multi-core processors for large vocabulary continuous speech recognition (LVCSR) requires changes in the recognizer architecture. In this paper, we consider how to parallelize the search component of a lexical-tree based speech recognizer. We introduce a hybrid-parallel method for dynamically dividing the lexical-tree copies among the cores at each frame. Each core is responsible for graph traversal in the lexical-tree copies allocated to it. This approach is compared to a previously-introduced static method that divides the lexical tree itself, so that each core is responsible for a different subtree of each of the lexical-tree copies. The new method outperforms the previous one when applied to the RWTH TC-STAR EPPS English LVCSR system running on four cores of an Intel Core-i7 processor with varying pruning-beam width settings.