Complete problems for logspace involving lexicographic first paths in graphs

DOI10.1007/3-540-55121-2_19MaRDI QIDQ4694732zbMATH OpenFDO

Authors Iain Stewart

Publication date 29 June 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55121-2_19

zbMATH Keywords

completenessdeterministic logspacedigraphlexicographic first pathreductionstranslations

Mathematics Subject Classification ID

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

Recommendations

• Problems complete for deterministic logarithmic space
• scientific article; zbMATH DE number 4060745
• scientific article; zbMATH DE number 4047154
• \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
• scientific article; zbMATH DE number 17799

Cited in

(4)

• Context-sensitive transitive closure operators
• A note on first-order projections and games.
• Problems complete for deterministic logarithmic space
• Methods for proving completeness via logical reductions

This page was built for publication: Complete problems for logspace involving lexicographic first paths in graphs

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