Spanning trees with edge conflicts and wireless connectivity

Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close - thus, the available pairs are specified with a link graph L = (V, E). Also, signal attenuation need not follow a nice geometric formula - hence, interference is modeled by a conflict (hyper)graph C = (E, F) on the links. The objective is to maximize the e ciency of the communication, or equivalently, to minimize the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the interference graph. Specifically, we give a simple algorithm that attains a O(ρ log n)-approximation, where n is the number of nodes and ρ is the inductive independence, and show that near-linear dependence on ρ is also necessary. We also treat an extension to Steiner trees, modeling multicasting, and obtain a comparable result. Our results suggest that several canonical assumptions of geometry, regularity and “niceness” in wireless settings can sometimes be relaxed without a significant hit in algorithm performance.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
StatePublished - Jul 1 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • Software


  • Aggregation
  • Approximation algorithms
  • Spanning trees
  • Wireless capacity


Dive into the research topics of 'Spanning trees with edge conflicts and wireless connectivity'. Together they form a unique fingerprint.

Cite this