Complexity of Deciding Sense of Direction

DOI10.1137/S0097539796310801MaRDI QIDQ4943845zbMATH OpenOpenAlexFDO

Authors Paolo Boldi, Sebastiano Vigna

Publication date 19 March 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539796310801

zbMATH Keywords

Cayley graphscomputational complexitydistributed systemssense of direction

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimal sense of direction and decision problems for Cayley graphs
• Sense of direction in distributed computing
• Symmetries and sense of direction in labeled graphs
• On the impact of sense of direction on message complexity
• scientific article; zbMATH DE number 1185591

Cited in

(12)

• Symmetries and sense of direction in labeled graphs
• Computing on anonymous networks with sense of direction
• Coverings that preserve sense of direction
• Lower bounds for weak sense of direction
• Sense of direction in distributed computing
• On the impact of sense of direction on message complexity
• Minimal sense of direction and decision problems for Cayley graphs
• OPTIMAL CONSTRUCTION OF SENSE OF DIRECTION IN A TORUS BY A MOBILE AGENT
• Lower bounds for sense of direction in regular graphs
• TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION
• scientific article; zbMATH DE number 6747941 (Why is no real title available?)
• Weak sense of direction labelings and graph embeddings

This page was built for publication: Complexity of Deciding Sense of Direction

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