<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5219</id>
    <completedYear/>
    <publishedYear>2004</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>343</pageFirst>
    <pageLast>370</pageLast>
    <pageNumber/>
    <edition/>
    <issue>3</issue>
    <volume>37</volume>
    <type>article</type>
    <publisherName>Springer Nature</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Congestion, dilation, and energy in radio networks</title>
    <abstract language="eng">We investigate the problem of path selection in radio networks for a given static set of n sites in two- and three-dimensional space. For static point-to-point communication we define measures for congestion, dilation, and energy consumption that take interferences among communication links into account. We show that energy-optimal path selection for radio networks can be computed in polynomial time. Then we introduce the diversity g(V) of a set V ⫅ ℝd for any constant d. It can be used to upper bound the number of interfering edges. For real-world applications it can be regarded as Θ(log n). A main result is that a c-spanner construction as a communication network allows one to approximate the congestion-optimal path system by a factor of O(g(V)2). Furthermore, we show that there are vertex sets where only one of the performance parameters congestion, dilation, and energy can be optimized at a time. We show trade-offs lower bounding congestion × dilation and dilation × energy. The trade-off between congestion and dilation increases with switching from two-dimensional to three-dimensional space. For congestion and energy the situation is even worse. It is only possible to find a reasonable approximation for either congestion or energy minimization, while the other parameter is at least a polynomial factor worse than in the optimal network.</abstract>
    <parentTitle language="eng">Theory of Computing Systems</parentTitle>
    <identifier type="doi">10.1007/s00224-004-1124-z</identifier>
    <enrichment key="opus.import.date">2022-08-20T07:06:56+00:00</enrichment>
    <enrichment key="opus.source">sword</enrichment>
    <enrichment key="opus.import.user">importuser</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <licence>Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG</licence>
    <author>Friedhelm Meyer auf der Heide</author>
    <author>Christian Schindelhauer</author>
    <author>Klaus Volbert</author>
    <author>Matthias Grünewald</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Medium Access Control</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Minimum Span Tree</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Communication Link</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Unit Energy</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Radio Station</value>
    </subject>
    <collection role="institutes" number="FakIM">Fakultät Informatik und Mathematik</collection>
    <collection role="othpublikationsherkunft" number="">Externe Publikationen</collection>
    <collection role="othforschungsschwerpunkt" number="16315">Information und Kommunikation</collection>
  </doc>
</export-example>
