Publications

← Magnús M. Halldórsson

104 entries, generated from BibTeX. Not hand-maintained.

2026

• Beyond Brooks: (Δ-1)-Coloring in Semi-Streaming
  Maxime Flin and Magnús M. Halldórsson
• Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
  Maxime Flin, Magnus M. Halldorsson, Manuel Jakob and Yannic Maus

2025

• Decentralized Distributed Graph Coloring: Cluster GraphsPODC 2025
  Maxime Flin, Magnus M. Halldorsson and Alexandre Nolin
• Faster Dynamic (Δ+1)-Coloring Against Adaptive AdversariesICALP 2025
  Maxime Flin and Magnus M. Halldorsson
• When MIS and Maximal Matching are Easy in the Congested CliqueTo Appear at SIROCCO
  Keren Censor-Hillel, Tomer Even, Maxime Flin and Magnus M. Halldorsson

2024

• A Distributed Palette Sparsification TheoremSODA 2024
  Maxime Flin, Mohsen Ghaffari, Magnus M. Halldorsson, Fabian Kuhn and Alexandre Nolin
• Decentralized Distributed Graph Coloring II: Degree+1-Coloring Virtual GraphsDISC 2024
  Maxime Flin, Magnus M. Halldorsson and Alexandre Nolin
• Distributed Delta-Coloring Under Bandwidth LimitationsDISC 2024
  Magnus M. Halldorsson and Yannic Maus
• Distributed Fractional Local Ratio and Independent Set Approximation31st SIROCCO
  Magnus M. Halldorsson and Dror Rawitz
• Distributed Lovasz Local Lemma under Bandwidth LimitationsCoRR
  Magnus M. Halldorsson, Yannic Maus and Saku Peltonen
• Distributed Lovász Local Lemma under Bandwidth Limitations
  Magnús M. Halldórsson, Yannic Maus and Saku Peltonen
• Distributed Δ-Coloring under Bandwidth LimitationsCoRR
  Yannic Maus and Magnus M. Halldorsson

2023

• Coloring Fast with BroadcastsSPAA 2023
  Maxime Flin, Mohsen Ghaffari, Magnus M. Halldorsson, Fabian Kuhn and Alexandre Nolin
• Distributed Coloring of HypergraphsSIROCCO
  Duncan Adamson, Magnus M. Halldorsson and Alexandre Nolin
• Fast Coloring Despite Congested RelaysDISC 2023
  Maxime Flin, Magnus M. Halldorsson and Alexandre Nolin
• Fast Distributed Brooks' TheoremSODA 2023
  Manuela Fischer, Magnus M. Halldorsson and Yannic Maus
• Superfast coloring in CONGEST via efficient color samplingTheor. Comput. Sci.
  Magnus M. Halldorsson and Alexandre Nolin

2022

• Fast Distributed Vertex Splitting with ApplicationsDISC 2022
  Magnus M. Halldorsson, Yannic Maus and Alexandre Nolin
• Near-optimal distributed degree+1 coloringSTOC 22
  Magnus M. Halldorsson, Fabian Kuhn, Alexandre Nolin and Tigran Tonoyan
• Overcoming Congestion in Distributed ColoringPODC 22
  Magnus M. Halldorsson, Alexandre Nolin and Tigran Tonoyan

2021

• Computing inductive vertex orderingsInformation Processing Letters
  Magnús M. Halldórsson and Tigran Tonoyan
• Efficient randomized distributed coloring in CONGESTSTOC 21
  Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus and Tigran Tonoyan
• Fast and Efficient Distributed Δ-ColoringSubmitted to this conference
  Manuela Fischer, Magnus M. Halldorsson and Yannic Maus
• Ultrafast Distributed Coloring
  Magnus M. Halldorsson, Fabian Kuhn, Alexandre Nolin and Tigran Tonoyan
• Ultrafast Distributed Coloring of High Degree GraphsCoRR
  Magnus M. Halldorsson, Alexandre Nolin and Tigran Tonoyan

2020

• Coloring Fast Without Learning Your Neighbors' ColorsDISC
  Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus and Alexandre Nolin
• Distance-2 Coloring in the CONGEST ModelPODC
  Magnus M. Halldorsson, Fabian Kuhn and Yannic Maus
• Distributed Testing of Distance-k ColoringsStructural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings
  Pierre Fraigniaud, Magnus M. Halldorsson and Alexandre Nolin
• Improved Distance-2 Coloring in the CONGEST Model
  Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus and Alexandre Nolin
• Improved distributed algorithms for coloring interval graphs with application to multicoloring treesTheor. Comput. Sci.
  Magnus M. Halldorsson and Christian Konrad
• Limitations of current wireless link scheduling algorithmsTheoretical Computer Science
  Magnus M. Halldorsson, Christian Konrad and Tigran Tonoyan
• Simple and local independent set approximationTheoretical Computer Science
  Ravi B Boppana, Magnus M Halldorsson and Dror Rawitz
• Sublinear algorithms for (Δ+1) vertex coloringTo appear in SIROCCO
  Pierre Fraigniaud, Magnus Halldorsson and Alexandre Nolin

2019

• Distributed Minimum Degree Spanning TreesProceedings of the ACM Symposium on the Principles of Distributed Computing (PODC)
  Michael Dinitz, Magnus M. Halldorsson, Taisuke Izumi and Calvin Newport
• Plain SINR is Enough!PODC 2019
  Magnus M. Halldorsson and Tigran Tonoyan
• Query-Competitive Sorting with UncertaintyMFCS
  M. M. Halldórsson and M. S. de Lima
• The Capacity of Smartphone Peer-To-Peer NetworksDISC
  Michael Dinitz, Magnus M. Halldorsson, Calvin Newport and Alex Weaver
• Wireless network algorithmicsComputing and Software Science: State of the Art and Perspectives
  Magnus M Halldorsson and Roger Wattenhofer

2018

• Computing Large Independent Sets in a Single RoundDistributed Computing
  Magnus M. Halldorsson and Christian Konrad
• Distributed Algorithms for Minimum Degree Spanning TreesarXiv preprint arXiv:1806.03365
  Michael Dinitz, Magnus M Halldorsson, Taisuke Izumi and Calvin Newport
• Effective Wireless Scheduling via Hypergraph SketchesCoRR
  Magnus M. Halldorsson and Tigran Tonoyan
• Leveraging Indirect Signaling for Topology Inference and Fast BroadcastPODC 18
  Magnus M. Halldorsson and Tigran Tonoyan
• Spanning Trees With Edge Conflicts and Wireless ConnectivityarXiv:1803.04578
  Magnus M. Halldorsson, Guy Kortsarz, Pradipta Mitra and Tigran Tonoyan
• Wireless Aggregation at Nearly Constant RateICDCS
  Magnus M. Halldorsson and Tigran Tonoyan

2017

• An Efficient Communication Abstraction for Dense Wireless NetworksDISC
  Magnus M. Halldorsson, Fabian Kuhn, Nancy A. Lynch and Calvin Newport
• Dynamic Adaptation in Wireless Networks Under Comprehensive Interference via Carrier SenseIPDPS 17
  Dongxiao Yu, Yuexuan Wang, Tigran Tonoyan and Magnus M. Halldorsson
• Leader Election in SINR Model with Arbitrary Power ControlSIROCCO'17
  Magnus M. Halldorsson, Stephan Holzer and Evangelia Anna Markatou
• Max point-tolerance graphsDiscrete Applied Mathematics
  Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halldórsson, Magnús M. Halldórsson, Thomas Hixon and Juraj Stacho
• Optimal Aggregation Throughput is Nearly ConstantMobihoc
  Magnus M. Halldorsson and Tigran Tonoyan
• Posimodular Function OptimizationProceedings of 15th International Symposium on Algorithms and Data Structures (WADS)
  Magnus M Halldorsson, Toshimasa Ishii, Kazuhisa Makino and Kenjiro Takazawa
• The Power of Oblivious Wireless PowerSIAM J. Comput.
  Magnus M. Halldorsson, Stephan Holzer, Pradipta Mitra and Roger Wattenhofer
• Universal Framework for Wireless Scheduling ProblemsICALP
  Eyjolfur Ingi Asgeirsson, Magnus M. Halldorsson and Tigran Tonoyan
• Wireless Link Capacity under Shadowing and FadingMobiHoc
  Magnus M. Halldorsson and Tigran Tonoyan

2016

• Brief Announcement: Local Independent Set ApproximationPODC
  Marijke H.L. Bodlaender, Magnus M. Halldorsson, Christian Konrad and Fabian Kuhn
• Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR ModelDistrib. Comput.
  Magnus M. Halldorsson and Pradipta Mitra
• Shrinking Maxima, Decreasing Costs: New Online Packing and Covering ProblemsALG
  Pierre Fraigniaud, Magnus M. Halldorsson, Boaz Patt-Shamir, Dror Rawitz and Adi Rosen
• Space-Constrained Interval SelectionACM Trans. Algorithms
  Yuval Emek, Magnus M. Halldorsson and Adi Rosen
• Streaming Algorithms for Independent Sets in Sparse HypergraphsAlgorithmica
  Bjarni V. Halldorsson, Magnus M. Halldorsson, Elena Losievskaja and Mario Szegedy

2015

• A Local Broadcast Layer for the SINR Network ModelPODC
  Magnus M. Halldorsson, Stephan Holzer and Nancy A. Lynch
• Distributed Large Independent Sets in One Round on Bounded-Independence GraphsDISC 2015
  Magnus M. Halldorsson and Christian Konrad
• How Well Can Graphs Represent Wireless Interference?STOC
  Magnus M. Halldorsson and Tigran Tonoyan
• Leveraging Multiple Channels in Ad Hoc NetworksPODC
  Magnus M. Halldorsson, Yuexuan Wang and Dongxiao Yu
• Limitations of Current Wireless Scheduling AlgorithmsAlgorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, Greece, September 17-18, 2015, Revised Selected Papers
  Magnus M. Halldorsson, Christian Konrad and Tigran Tonoyan
• Radio Aggregation SchedulingAlgosensors
  Rajiv Gandhi, Magnus M. Halldorsson, Christian Konrad, Guy Kortsarz and Hoon Oh
• The Price of Local Power Control in Wireless SchedulingFSTTCS
  Magnus M. Halldorsson and Tigran Tonoyan
• Vertex coloring edge-weighted digraphsInf. Process. Lett.
  Jørgen Bang-Jensen and Magnus M. Halldorsson

2014

• Algorithms for wireless capacityIEEE/ACM Transactions on Networking (TON)
  Olga Goussevskaia, Magnus M Halldorsson and Roger Wattenhofer
• Beyond geometry: towards fully realistic wireless modelsPODC
  Marijke H. L. Bodlaender and Magnus M. Halldorsson
• Distributed Algorithms for Coloring interval GraphsProceedings of the 28th International Conference on Distributed Computing
  Magnus M. Halldorsson and Christian Konrad
• Extending wireless algorithm design to arbitrary environments via metricityMSWiM
  Helga Gudmundsdottir, Eyjolfur Ingi Asgeirsson, Marijke H. L. Bodlaender, Joseph T. Foley, Magnus M. Halldorsson and Ymir Vigfusson
• Making Wireless Algorithm Theory More Useful: Five Ideas From the 2013 Workshop on Realistic Models for Algorithms in Wireless NetworksACM SIGACT News
  Magnus Halldorsson and Calvin Newport
• Maximum MIMO Flow in wireless networks under the SINR modelWiOpt
  Eyjolfur Ingi Asgeirsson, Magnus M. Halldorsson and Pradipta Mitra
• Measurement Based Interference Models for Wireless Scheduling AlgorithmsMSWiM
  Helga Gudmundsdottir, Eyjolfur I. Asgeirsson, Marijke Bodlaender, Joseph T. Foley, Magnus M. Halldorsson and Ymir Vigfusson
• Wireless Scheduling Algorithms in Complex Environmentshttp://arxiv.org/abs/1401.1723
  Helga Gudmundsdottir, Eyjolfur I. Asgeirsson, Marijke Bodlaender, Joseph T. Foley, Magnus M. Halldorsson and Ymir Vigfusson

2013

• Beyond Basic SINR: Modeling Spatial Variability in Wireless Networks
  Marijke H. L. Bodlaender and Magnus M. Halldorsson
• Connectivity and aggregation in multihop wireless networksPODC 13
  Marijke H. L. Bodlaender, Magnus M. Halldorsson and Pradipta Mitra
• Online Scheduling with Interval ConflictsTOCS
  Magnus M. Halldorsson, Boaz Patt-Shamir and Dror Rawitz
• Online selection of intervals and t-intervalsInformation and Computation
  Unnar Th. Bachmann, Magnus M. Halldorsson and Hadas Shachnai
• The Power of Non-Uniform Wireless PowerSODA
  Magnus M. Halldorsson, Stephan Holzer, Pradipta Mitra and Roger Wattenhofer

2012

• A fully distributed algorithm for throughput performance in wireless networksCISS
  Eyjolfur Ingi Asgeirsson, Magnus M. Halldorsson and Pradipta Mitra
• Distributed connectivity of wireless networksPODC
  Magnus M. Halldorsson and Pradipta Mitra
• On the Impact of Identifiers on Local DecisionOPODIS
  Pierre Fraigniaud, Magnus M. Halldorsson and Amos Korman
• Online set packingSIAM Journal of Computing
  Yuval Emek, Magnus M. Halldorsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan and Dror Rawitz
• Towards tight bounds for local broadcastingFOMC
  Magnus M. Halldorsson and Pradipta Mitra
• Wireless Network Stability in the SINR ModelSIROCCO
  Eyjolfur Ingi Asgeirsson, Magnus M. Halldorsson and Pradipta Mitra
• Wireless Scheduling with Power ControlACM Trans. Algorithms
  Magnus M. Halldorsson
• Wireless capacity and admission control in cognitive radioInfocom
  Magnus M. Halldorsson and Pradipta Mitra
• Wireless connectivity and capacitySODA
  Magnus M. Halldorsson and Pradipta Mitra

2011

• Wireless Capacity with Arbitrary Gain MatrixALGOSENSORS
  Magnus M. Halldorsson and Pradipta Mitra
• Wireless Capacity with Oblivious Power in General MetricsSODA
  Magnus M. Halldorsson and Pradipta Mitra

2010

• Online Set Packing and Competitive Scheduling of Multi-Part TasksPODC 10
  Yuval Emek, Magnus M. Halldorsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan and Dror Rawitz
• Streaming Algorithms for Independent SetsICALP (1)
  Bjarni V. Halldorsson, Magnus M. Halldorsson, Elena Losievskaja and Mario Szegedy

2009

• Capacity of Arbitrary Wireless Networks28th Annual IEEE Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil
  Olga Goussevskaia, Magnus M. Halldorsson, Roger Wattenhofer and Emo Welzl
• Wireless Communication is in APXICALP
  M. M. Halldorsson and R. Wattenhofer

2006

• Scheduling Split IntervalsSICOMP
  Reuven Bar-Yehuda, Magnus M. Halldorsson, Joseph Naor, Hadas Shachnai and Irina Shapira

2004

• Approximations of weighted independent set and hereditary subset problemsGraph Algorithms And Applications 2
  Magnus M Halldorsson

2003

• Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent JobsAlgorithmica
  Magnus M. Halldorsson, Guy Kortsarz and Hadas Shachnai

2002

• Approximating thedomatic numberSIAM Journal on computing
  Uriel Feige, Magnus M Halldorsson, Guy Kortsarz and Aravind Srinivasan

2000

• Independent Sets with Domination ConstraintsDAM
  Magnus M. Halldorsson, Jan Kratochv\'l and Jan Arne Telle

1997

• Greed is Good: Approximating Independent Sets in Sparse and Bounded-degree GraphsAlgorithmica
  Magnus Halldorsson and Jaikumar Radhakrishnan
• Parallel and On-Line Graph ColoringJ. Algorithms
  Magnus M. Halldorsson

1994

• Lower Bounds for On-Line Graph ColoringTheor. Comput. Sci.
  Magnus M. Halldorsson and Mario Szegedy

1993

• A Still Better Performance Guarantee for Approximate Graph ColoringInf. Process. Lett.
  Magnus M. Halldorsson
• Approximating the Minimum Maximal Independence NumberInf. Process. Lett.
  Magnus M. Halldorsson