EUVIMEDEUVIMED entdecken
Crossref

A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem

Kaixiang Hu, Xiankai Li, Caixia Kou

International Journal of Foundations of Computer Science · 16.07.2026 · 1-14

DOI: 10.1142/s0129054126430033 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 16.07.2026. Verfasst von Kaixiang Hu und 2 weiteren Autor:innen. Gefördert von: Beijing Natural Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Finding a routing path that satisfies two independent additive constraints (e.g., delay and cost) is a critical requirement in quality of service (QoS) routing. While this two-constraint path problem is NP-Hard, it is prevalent in practical network applications. Existing solutions typically face a trade-off: heuristics lack feasibility guarantees, while exact algorithms suffer from exponential computational complexity. In this paper, we propose a dual-guided exact algorithm that effectively bridges the gap between the computational efficiency of Lagrangian relaxation and the optimality guarantees of combinatorial search. Our method first solves the Lagrangian dual problem to derive the optimal multiplier, which subsequently serves as the optimal aggregate coefficient to guide a heuristic A*-prune search. This hybrid mechanism allows the algorithm to efficiently prune the search space while guaranteeing the identification of a cost-efficient feasible solution. Numerical experiments on random network topologies demonstrate that the proposed algorithm significantly outperforms the standard A*-prune algorithm while maintaining exactness. Specifically, in networks with up to 500 nodes, our method reduces the execution time by orders of magnitude compared to traditional exact methods.

Förderung

  • Beijing Natural Science Foundation

Zitieren

APA

Hu, K., Li, X., & Kou, C. (2026). A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem. International Journal of Foundations of Computer Science, 1-14. https://doi.org/10.1142/s0129054126430033

Vancouver

Hu K, Li X, Kou C. A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem. International Journal of Foundations of Computer Science. 2026:1-14. doi:10.1142/s0129054126430033

BibTeX
@article{Hu2026,
  author = {Hu, Kaixiang and Li, Xiankai and Kou, Caixia},
  title = {A Dual-Guided Exact Algorithm for the Two-Constraint Path Problem},
  journal = {International Journal of Foundations of Computer Science},
  year = {2026},
  pages = {1--14},
  doi = {10.1142/s0129054126430033}
}
Kostenlos starten →