The Complexity of Restricted Variants of the Stable Paths Problem

DOI10.3233/FI-2010-319MaRDI QIDQ3000275zbMATHOpenAlexFDO

Authors Kevin Donnelly, Assaf Kfoury, Andrei Lapets

Publication date 18 May 2011

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2010-319

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Internet topics (68M11) Network protocols (68M12)

Recommendations

• On the stable paths problem
• On the complexity of vertex-disjoint length-restricted path problems
• scientific article; zbMATH DE number 2061547
• On the computational complexity of length- and neighborhood-constrained path problems
• scientific article; zbMATH DE number 509206
• On the computational complexity of path cover problems
• On the stability of approximation for Hamiltonian path problems
• SOFSEM 2005: Theory and Practice of Computer Science
• Complexity of the path avoiding forbidden pairs problem revisited
• scientific article; zbMATH DE number 4202050

Cited in

(13)

• Computational complexity of traffic hijacking under BGP and S-BGP
• scientific article; zbMATH DE number 2061547 (Why is no real title available?)
• Computational complexity of traffic hijacking under BGP and S-BGP
• scientific article; zbMATH DE number 3934720 (Why is no real title available?)
• On the stable paths problem
• Subjective-cost policy routing
• On the complexity of the Eulerian closed walk with precedence path constraints problem
• On the complexity of the Eulerian closed walk with precedence path constraints problem
• Minimum failure explanations for path vector routing changes
• Domain clustering for inter-domain path computation speed-up
• Acyclic Type-of-Relationship Problems on the Internet
• On the convergence time of a path-vector protocol
• Complexity of the path avoiding forbidden pairs problem revisited

This page was built for publication: The Complexity of Restricted Variants of the Stable Paths Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000275)