3 Search Results for "Niebert, Peter"

Document
DOI: 10.4230/LIPIcs.MFCS.2018.39
Balanced Connected Partitioning of Unweighted Grid Graphs

Authors: Cedric Berenger, Peter Niebert, and Kevin Perrot

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We consider a partitioning problem for grid graphs with special constraints: a (square) grid graph as well as a number of colors is given, a solution is a coloring approximatively assigning the same number of vertices to each color and such that the induced subgraph for each color is connected. In a "rooted" variant, a vertex to be included in the coloring for each color is specified as well. This problem has a concrete motivation in multimedia streaming applications. We show that the general problem is NP-complete. On the other hand, we define a reasonable easy subclass of grid graphs for which solutions always exist and can be computed by a greedy algorithm.
Cite as

Cedric Berenger, Peter Niebert, and Kevin Perrot. Balanced Connected Partitioning of Unweighted Grid Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{berenger_et_al:LIPIcs.MFCS.2018.39,
  author =	{Berenger, Cedric and Niebert, Peter and Perrot, Kevin},
  title =	{{Balanced Connected Partitioning of Unweighted Grid Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.39},
  URN =		{urn:nbn:de:0030-drops-96213},
  doi =		{10.4230/LIPIcs.MFCS.2018.39},
  annote =	{Keywords: grid graphs, connected partitioning, NP-completeness, graph algorithm}
}
Document
DOI: 10.4230/LITES-v002-i002-a001
From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation

Authors: Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens

Published in: LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2

Abstract
Our objective is to facilitate the development of complex time-triggered systems by automating the allocation and scheduling steps. We show that full automation is possible while taking into account the elements of complexity needed by a complex embedded control system. More precisely, we consider deterministic functional specifications provided (as often in an industrial setting) by means of synchronous data-flow models with multiple modes and multiple relative periods. We first extend this functional model with an original real-time characterization that takes advantage of our time-triggered framework to provide a simpler representation of complex end-to-end flow requirements. We also extend our specifications with additional non-functional properties specifying partitioning, allocation, and preemptability constraints. Then, we provide novel algorithms for the off-line scheduling of these extended specifications onto partitioned time-triggered architectures à la ARINC 653. The main originality of our work is that it takes into account at the same time multiple complexity elements: various types of non-functional properties (real-time, partitioning, allocation, preemptability) and functional specifications with conditional execution and multiple modes. Allocation of time slots/windows to partitions can be fully or partially provided, or synthesized by our tool. Our algorithms allow the automatic allocation and scheduling onto multi-processor (distributed) systems with a global time base, taking into account communication costs. We demonstrate our technique on a model of space flight software system with strong real-time determinism requirements.
Cite as

Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens. From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation. In LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2, pp. 01:1-01:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{carle_et_al:LITES-v002-i002-a001,
  author =	{Carle, Thomas and Potop-Butucaru, Dumitru and Sorel, Yves and Lesens, David},
  title =	{{From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:30},
  ISSN =	{2199-2002},
  year =	{2015},
  volume =	{2},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v002-i002-a001},
  URN =		{urn:nbn:de:0030-drops-192540},
  doi =		{10.4230/LITES-v002-i002-a001},
  annote =	{Keywords: Time-triggered, Off-line real-time scheduling, Temporal partitioning}
}
Document
DOI: 10.4230/DagSemRep.254
Temporal Logics for Distributed Systems - Paradigms and Algorithms (Dagstuhl Seminar 99411)

Authors: Edmund M. Clarke, Ursula Goltz, Peter Niebert, and Wojciech Penczek

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Edmund M. Clarke, Ursula Goltz, Peter Niebert, and Wojciech Penczek. Temporal Logics for Distributed Systems - Paradigms and Algorithms (Dagstuhl Seminar 99411). Dagstuhl Seminar Report 254, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{clarke_et_al:DagSemRep.254,
  author =	{Clarke, Edmund M. and Goltz, Ursula and Niebert, Peter and Penczek, Wojciech},
  title =	{{Temporal Logics for Distributed Systems - Paradigms and Algorithms (Dagstuhl Seminar 99411)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{254},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.254},
  URN =		{urn:nbn:de:0030-drops-151402},
  doi =		{10.4230/DagSemRep.254},
}
  • Refine by Type
  • 3 Document/PDF

  • Refine by Publication Year
  • 1 2018
  • 1 2015
  • 1 2000

  • Refine by Author
  • 2 Niebert, Peter
  • 1 Berenger, Cedric
  • 1 Carle, Thomas
  • 1 Clarke, Edmund M.
  • 1 Goltz, Ursula
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 LITES
  • 1 DagSemRep

  • Refine by Classification
  • 1 Computer systems organization
  • 1 Computer systems organization → Real-time systems
  • 1 Hardware → Partitioning and floorplanning
  • 1 Mathematics of computing → Paths and connectivity problems

  • Refine by Keyword
  • 1 NP-completeness
  • 1 Off-line real-time scheduling
  • 1 Temporal partitioning
  • 1 Time-triggered
  • 1 connected partitioning
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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