Some combinatorial aspects of time-stamp systems
type: Item
instance of: scholarly article
title: Some combinatorial aspects of time-stamp systems
zbMATH Open document ID: 0771.05043
author: Robert Cori
author: Éric Sopena
published in: European Journal of Combinatorics
publication date: 1993-05-16T00:00:00Z
review text: An ordered \(k\)-sequence is a sequence \((y_ 1,\dots,y_ k)\) of vertices of an oriented graph \(G\) such that if \(1\leq i<j\leq k\) then the arc \((y_ i,y_ j)\) is in \(G\). An oriented graph \(G\) is a \(p\)-restricted time- stamp system of order \(k\) if there exists a family \({\mathcal F}\) of ordered \(k\)-sequences of vertices of \(G\) such that (a) every vertex of \(G\) belongs to some element of \({\mathcal F}\), and (b) if \((u_ 1,\dots,u_ k)\) is an element of \({\mathcal F}\) and \(i\leq p\) then there is a vertex \(v\) such that \((u_ 1,\dots,u_{i-1},u_{i+1},\dots,u_ k,v)\) is an element of \({\mathcal F}\). The authors show, among other things, that there exists a \(p\)-restricted time-stamp system of order \(k\) with \(p2^{p-1}(2k-2p+1)\) vertices.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 168331
zbMATH Keywords: distributed computing
zbMATH Keywords: oriented graph
zbMATH Keywords: time-stamp system
reviewed by: J. W. Moon
MaRDI profile type: Publication
OpenAlex ID: W2016423197
DOI: 10.1006/EUJC.1993.1013
Recommended article: A combinatorial approach to time asymmetry
Recommended article: Information Security
Recommended article: Q4249353
Recommended article: On Provably Secure Time-Stamping Schemes
Recommended article: The timestamp of timed automata
Recommended article: SOME PROPERTIES OF LINKED TIME SYSTEMS
Recommended article: The combinatorics of discrete time-trees: theory and open problems
Recommended article: On the stability of timed token rings
Recommended article: On the design of time-stamped signatures
description: scientific article; zbMATH DE number 168331