1 Search Results for "Mitra, Pradipta"


Document
Spanning Trees With Edge Conflicts and Wireless Connectivity

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

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
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 efficiency 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(rho log n)-approximation, where n is the number of nodes and rho is the inductive independence, and show that near-linear dependence on rho 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.

Cite as

Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, and Tigran Tonoyan. Spanning Trees With Edge Conflicts and Wireless Connectivity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 158:1-158:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.ICALP.2018.158,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Kortsarz, Guy and Mitra, Pradipta and Tonoyan, Tigran},
  title =	{{Spanning Trees With Edge Conflicts and Wireless Connectivity}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{158:1--158:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.158},
  URN =		{urn:nbn:de:0030-drops-91627},
  doi =		{10.4230/LIPIcs.ICALP.2018.158},
  annote =	{Keywords: spanning trees, wireless capacity, aggregation, approximation algorithms}
}
  • Refine by Author
  • 1 Halldórsson, Magnús M.
  • 1 Kortsarz, Guy
  • 1 Mitra, Pradipta
  • 1 Tonoyan, Tigran

  • Refine by Classification
  • 1 Networks → Network design and planning algorithms
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 aggregation
  • 1 approximation algorithms
  • 1 spanning trees
  • 1 wireless capacity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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