2 Search Results for "Pop, Paul"

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.53
Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time

Authors: Paul Lapey and Aaron Williams

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
The number of ordered trees (also known as plane trees) with n nodes is the (n-1)st Catalan number C_{n-1}. An ordered tree can be stored directly using nodes and pointers, or represented indirectly by a Dyck word. This paper presents a loopless algorithm for generating ordered trees with n nodes using pointer-based representations. In other words, we spend 𝒪(C_{n-1})-time to generate all of the trees, and moreover, the delay between consecutive trees is worst-case 𝒪(1)-time. To achieve this run-time, each tree must differ from the previous by a constant amount. In other words, the algorithm must create a type of Gray code order. Our algorithm operates on the children of a node like a stack, by popping the first child off of one node’s stack and pushing the result onto another node’s stack. We refer to this pop-push operation as a pull, and consecutive trees in our order differ by one or two pulls. There is a simple two-case successor rule that determines the pulls to apply directly from the current tree. When converted to Dyck words, our rule corresponds to a left-shift, and these shift generate a cool-lex variant of lexicographic order. Our results represent the first pull Gray code for ordered trees, and the first fully published loopless algorithm for ordered trees using pointer representations. More importantly, our algorithm is incredibly simple: A full implementation in C, including initialization and output, uses only three loops and three if-else blocks. Our work also establishes a simultaneous Gray code for Dyck words, ordered trees, and also binary trees, using cool-lex order.
Cite as

Paul Lapey and Aaron Williams. Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lapey_et_al:LIPIcs.ISAAC.2022.53,
  author =	{Lapey, Paul and Williams, Aaron},
  title =	{{Pop \& Push: Ordered Tree Iteration in 𝒪(1)-Time}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.53},
  URN =		{urn:nbn:de:0030-drops-173380},
  doi =		{10.4230/LIPIcs.ISAAC.2022.53},
  annote =	{Keywords: combinatorial generation, Gray code, simultaneous Gray code, ordered trees, plane trees, Dyck words, binary trees, Catalan objects, loopless algorithm, cool-lex order}
}
Document
DOI: 10.4230/OASIcs.Fog-IoT.2020.3
Quality-Of-Control-Aware Scheduling of Communication in TSN-Based Fog Computing Platforms Using Constraint Programming

Authors: Mohammadreza Barzegaran, Bahram Zarrin, and Paul Pop

Published in: OASIcs, Volume 80, 2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020)

Abstract
In this paper we are interested in real-time control applications that are implemented using Fog Computing Platforms consisting of interconnected heterogeneous Fog Nodes (FNs). Similar to previous research and ongoing standardization efforts, we assume that the communication between FNs is achieved via IEEE 802.1 Time Sensitive Networking (TSN). We model the control applications as a set of real-time streams, and we assume that the messages are transmitted using time-sensitive traffic that is scheduled using the Gate Control Lists (GCLs) in TSN. Given a network topology and a set of control applications, we are interested to synthesize the GCLs for messages such that the quality-of-control of applications is maximized and the deadlines of real-time messages are satisfied. We have proposed a Constraint Programming-based solution to this problem, and evaluated it on several test cases.
Cite as

Mohammadreza Barzegaran, Bahram Zarrin, and Paul Pop. Quality-Of-Control-Aware Scheduling of Communication in TSN-Based Fog Computing Platforms Using Constraint Programming. In 2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020). Open Access Series in Informatics (OASIcs), Volume 80, pp. 3:1-3:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barzegaran_et_al:OASIcs.Fog-IoT.2020.3,
  author =	{Barzegaran, Mohammadreza and Zarrin, Bahram and Pop, Paul},
  title =	{{Quality-Of-Control-Aware Scheduling of Communication in TSN-Based Fog Computing Platforms Using Constraint Programming}},
  booktitle =	{2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020)},
  pages =	{3:1--3:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-144-3},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{80},
  editor =	{Cervin, Anton and Yang, Yang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Fog-IoT.2020.3},
  URN =		{urn:nbn:de:0030-drops-119975},
  doi =		{10.4230/OASIcs.Fog-IoT.2020.3},
  annote =	{Keywords: TSN, Fog Computing, Constraint Programming, Quality of Control}
}
  • Refine by Author
  • 1 Barzegaran, Mohammadreza
  • 1 Lapey, Paul
  • 1 Pop, Paul
  • 1 Williams, Aaron
  • 1 Zarrin, Bahram

  • Refine by Classification
  • 1 Computer systems organization → Embedded software
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorics
  • 1 Networks → Traffic engineering algorithms
  • 1 Theory of computation → Constraint and logic programming
  • Show More...

  • Refine by Keyword
  • 1 Catalan objects
  • 1 Constraint Programming
  • 1 Dyck words
  • 1 Fog Computing
  • 1 Gray code
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact