.png){kind=icon}
Return
Step Systems on Graphs
.png){kind=icon}
OA
AI
DOI：10.1007/s10013-026-00808-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Step systems of connected graphs were introduced by Ladislav Nebesk & yacute; as a means of describing shortest paths solely in terms of local information. A ternary relation T encodes, for each point u, the first step x towards a target v. Eight first-order axioms characterize the ternary relation T that are step systems. Here we show that one of Nebesk & yacute;'s eight axioms is in fact redundant. Moreover, we characterize the step systems of bipartite graphs, partial cubes, and weakly modular graphs in terms of first-order axioms. In each case we show that the corresponding sets of axioms are non-redundant.
Keywords:
Signpost systems
Independency of axioms
Bipartite graphs
Partial cubes
Weakly modular graphs
Journal
V
IF:
0.7
Papers:
45
Citations:
0
Organization
Cited Papers
ShareSaveMemory requirement for routing in distributed networks.png)
Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing - PODC '96
OAAI
Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing - PODC '96IF0
OAAIShareSaveShareSaveShareSaveShareSaveShareSave
View more