On legal path problems in digraphs

DOI10.1016/0020-0190(84)90030-9zbMATH Open0534.68047OpenAlexW2094658183MaRDI QIDQ790621FDOQ790621

Authors: Heung-Soon Ihm, Simeon C. Ntafos 

Publication date: 1984

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(84)90030-9

Recommendations

• On the computational complexity of path cover problems
• On paths avoding forbidden pairs of vertices in a graph
• Parallelism and the maximal path problem
• scientific article; zbMATH DE number 3948312
• Maximum path digraphs

zbMATH Keywords

NP-completenessefficient algorithmprogram testingimpossible path, legal path

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of software (68N99)

Cites Work

• On Path Cover Problems in Digraphs and Applications to Program Testing
• `` Strong NP-Completeness Results
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Unified Approach to Path Problems

Cited In (1)

• On the computational complexity of path cover problems

This page was built for publication: On legal path problems in digraphs

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