Böltz, Lucas ; Becker, Benjamin ; Frey, Hannes (2021)
Local Construction of Connected Plane Subgraphs in Graphs Satisfying Redundancy and Coexistence.
In: Procedia Computer Science, 195
doi: 10.1016/j.procs.2021.11.016
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
Connected plane graphs enable many local algorithmic solutions for data communication, task coordination and network maintenance in wireless sensor networks, sensor-actuator networks and distributed robotics. We study construction of such graphs by removing edges from a given network graph. We assume redundancy and coexistence, a graph structure which holds in realistic wireless network models with high probability and which assures that a connected plane graph can always be constructed with local edge removal rules. We present a local algorithm to construct such a connected plane graph. We prove algorithm correctness under redundancy and coexistence assumption. Furthermore, we discuss how far redundancy and coexistence could be weakened while still assuring correctness of the algorithm.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2021 |
| Autor(en): | Böltz, Lucas ; Becker, Benjamin ; Frey, Hannes |
| Art des Eintrags: | Bibliographie |
| Titel: | Local Construction of Connected Plane Subgraphs in Graphs Satisfying Redundancy and Coexistence |
| Sprache: | Englisch |
| Publikationsjahr: | 2021 |
| Verlag: | Elsevier |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Procedia Computer Science |
| Jahrgang/Volume einer Zeitschrift: | 195 |
| DOI: | 10.1016/j.procs.2021.11.016 |
| Kurzbeschreibung (Abstract): | Connected plane graphs enable many local algorithmic solutions for data communication, task coordination and network maintenance in wireless sensor networks, sensor-actuator networks and distributed robotics. We study construction of such graphs by removing edges from a given network graph. We assume redundancy and coexistence, a graph structure which holds in realistic wireless network models with high probability and which assures that a connected plane graph can always be constructed with local edge removal rules. We present a local algorithm to construct such a connected plane graph. We prove algorithm correctness under redundancy and coexistence assumption. Furthermore, we discuss how far redundancy and coexistence could be weakened while still assuring correctness of the algorithm. |
| Fachbereich(e)/-gebiet(e): | 18 Fachbereich Elektrotechnik und Informationstechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik > Multimedia Kommunikation |
| Hinterlegungsdatum: | 04 Mai 2023 08:53 |
| Letzte Änderung: | 01 Aug 2023 08:52 |
| PPN: | 510057632 |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum