Publications

← Magnús M. Halldórsson

255 entries, generated from DBLP. Not hand-maintained. Citation counts on Google Scholar.

2026

• Beyond Brooks: (Δ-1)-Coloring in Semi-StreamingICALP arXiv
  Maxime Flin and Magnús M. Halldórsson
• Robust Shattering ArgumentsarXiv
  Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus and Alexandre Nolin
• Sublogarithmic Distributed Vertex Coloring with Optimal Number of ColorsSTOC arXiv
  Maxime Flin, Magnús M. Halldórsson, Manuel Jakob and Yannic Maus
• Unit Interval Selection in Random Order StreamsSTACS arXiv
  Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad and Kheeran K. Naidu

2025

• Approximating Independent Sets in Constant Distributed RoundsSIROCCO
  Ravi B. Boppana and Magnús M. Halldórsson
• Decentralized Distributed Graph Coloring: Cluster GraphsPODC arXiv
  Maxime Flin, Magnús M. Halldórsson and Alexandre Nolin
• Distributed fractional local ratio and independent set approximationInf. Comput.
  Magnús M. Halldórsson and Dror Rawitz
• Faster Dynamic (Δ+1)-Coloring Against Adaptive AdversariesICALP arXiv
  Maxime Flin and Magnús M. Halldórsson
• Streaming Diameter of High-Dimensional PointsESA arXiv
  Magnús M. Halldórsson, Nicolaos Matsakis and Pavel Veselý
• When MIS and Maximal Matching are Easy in the Congested CliqueSIROCCO arXiv
  Keren Censor-Hillel, Tomer Even, Maxime Flin and Magnús M. Halldórsson

2024

• A Distributed Palette Sparsification TheoremSODA arXiv
  Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kuhn and Alexandre Nolin
• Decentralized Distributed Graph Coloring II: Degree+1-Coloring Virtual GraphsDISC arXiv
  Maxime Flin, Magnús M. Halldórsson and Alexandre Nolin
• Distributed Delta-Coloring Under Bandwidth LimitationsDISC arXiv
  Magnús M. Halldórsson and Yannic Maus
• Distributed Fractional Local Ratio and Independent Set ApproximationSIROCCO
  Magnús M. Halldórsson and Dror Rawitz
• Distributed Lovász Local Lemma under Bandwidth LimitationsarXiv
  Magnús M. Halldórsson, Yannic Maus and Saku Peltonen
• Online Multiset Submodular CoverAlgorithmica
  Magnús M. Halldórsson and Dror Rawitz

2023

• Coloring Fast with BroadcastsSPAA arXiv
  Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kuhn and Alexandre Nolin
• Distributed Coloring of HypergraphsSIROCCO
  Duncan Adamson, Magnús M. Halldórsson and Alexandre Nolin
• Fast Coloring Despite Congested RelaysDISC arXiv
  Maxime Flin, Magnús M. Halldórsson and Alexandre Nolin
• Fast Distributed Brooks' TheoremSODA arXiv
  Manuela Fischer, Magnús M. Halldórsson and Yannic Maus
• SIROCCO Prize for Innovation in Distributed Computing - Laudatio for Boaz Patt-ShamirBull. EATCS
  Magnús M. Halldórsson
• Superfast coloring in CONGEST via efficient color samplingTheor. Comput. Sci. arXiv
  Magnús M. Halldórsson and Alexandre Nolin

2022

• Fast Distributed Vertex Splitting with ApplicationsDISC arXiv
  Magnús M. Halldórsson, Yannic Maus and Alexandre Nolin
• Near-optimal distributed degree+1 coloringSTOC arXiv
  Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin and Tigran Tonoyan
• Overcoming Congestion in Distributed ColoringPODC arXiv
  Magnús M. Halldórsson, Alexandre Nolin and Tigran Tonoyan
• Posimodular Function OptimizationAlgorithmica
  Magnús M. Halldórsson, Toshimasa Ishii, Kazuhisa Makino and Kenjiro Takazawa

2021

• Computing inductive vertex orderingsInf. Process. Lett.
  Magnús M. Halldórsson and Tigran Tonoyan
• Effective Wireless Scheduling via Hypergraph SketchesSIAM J. Comput. arXiv
  Magnús M. Halldórsson and Tigran Tonoyan
• Efficient randomized distributed coloring in CONGESTSTOC arXiv
  Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus and Tigran Tonoyan
• Generalized Disk GraphsWADS
  Ívar Marrow Arnþórsson, Steven Chaplick, Jökull Snær Gylfason, Magnús M. Halldórsson, Jökull Máni Reynisson and Tigran Tonoyan
• Local improvement algorithms for a path packing problem: A performance analysis based on linear programmingOper. Res. Lett.
  Koen M. J. De Bontridder, Bjarni V. Halldórsson, Magnús M. Halldórsson, Cor A. J. Hurkens, Jan Karel Lenstra, R. Ravi and Leen Stougie
• Network Design under General Wireless InterferenceAlgorithmica
  Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra and Tigran Tonoyan
• Query minimization under stochastic uncertaintyTheor. Comput. Sci. arXiv
  Steven Chaplick, Magnús M. Halldórsson, Murilo S. de Lima and Tigran Tonoyan
• Query-competitive sorting with uncertaintyTheor. Comput. Sci. arXiv
  Magnús M. Halldórsson and Murilo Santos de Lima
• Sparse Backbone and Optimal Distributed SINR AlgorithmsACM Trans. Algorithms
  Magnús M. Halldórsson and Tigran Tonoyan
• Superfast Coloring in CONGEST via Efficient Color SamplingSIROCCO
  Magnús M. Halldórsson and Alexandre Nolin
• Ultrafast Distributed Coloring of High Degree GraphsarXiv
  Magnús M. Halldórsson, Alexandre Nolin and Tigran Tonoyan

2020

• Coloring Fast Without Learning Your Neighbors' ColorsDISC arXiv
  Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus and Alexandre Nolin
• Distance-2 Coloring in the CONGEST ModelPODC arXiv
  Magnús M. Halldórsson, Fabian Kuhn and Yannic Maus
• Distributed Testing of Distance-k ColoringsSIROCCO
  Pierre Fraigniaud, Magnús M. Halldórsson and Alexandre Nolin
• Improved distributed algorithms for coloring interval graphs with application to multicoloring treesTheor. Comput. Sci.
  Magnús M. Halldórsson and Christian Konrad
• Leader election in SINR model with arbitrary power controlTheor. Comput. Sci.
  Magnús M. Halldórsson, Stephan Holzer, Evangelia Anna Markatou and Nancy A. Lynch
• Limitations of current wireless link scheduling algorithmsTheor. Comput. Sci.
  Magnús M. Halldórsson, Christian Konrad and Tigran Tonoyan
• Query Minimization Under Stochastic UncertaintyLATIN
  Steven Chaplick, Magnús M. Halldórsson, Murilo Santos de Lima and Tigran Tonoyan
• Radio aggregation schedulingTheor. Comput. Sci.
  Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz and Hoon Oh
• Simple and local independent set approximationTheor. Comput. Sci. arXiv
  Ravi B. Boppana, Magnús M. Halldórsson and Dror Rawitz
• Tight Bounds on Subexponential Time Approximation of Set Cover and Related ProblemsWAOA arXiv
  Magnús M. Halldórsson, Guy Kortsarz and Marek Cygan

2019

• Distributed Minimum Degree Spanning TreesPODC
  Michael Dinitz, Magnús M. Halldórsson, Taisuke Izumi and Calvin Newport
• Distributed approximation of k-service assignmentDistributed Comput.
  Magnús M. Halldórsson, Sven Köhler and Dror Rawitz
• Leveraging multiple channels in ad hoc networksDistributed Comput. arXiv
  Magnús M. Halldórsson, Yuexuan Wang and Dongxiao Yu
• Link Scheduling under Correlated ShadowingWiOpt
  Magnús M. Halldórsson and Tigran Tonoyan
• Plain SINR is Enough!PODC
  Magnús M. Halldórsson and Tigran Tonoyan
• Query-Competitive Sorting with UncertaintyMFCS
  Magnús M. Halldórsson and Murilo Santos de Lima
• The Capacity of Smartphone Peer-To-Peer NetworksDISC arXiv
  Michael Dinitz, Magnús M. Halldórsson, Calvin Newport and Alex Weaver
• Wireless Network AlgorithmicsComputing and Software Science
  Magnús M. Halldórsson and Roger Wattenhofer

2018

• Algorithms for Chromatic Sums, Multicoloring, and Scheduling Dependent JobsHandbook of Approximation Algorithms and Metaheuristics (1)
  Magnús M. Halldórsson and Guy Kortsarz
• Brief Announcement: Simple and Local Independent Set ApproximationPODC
  Ravi B. Boppana, Magnús M. Halldórsson and Dror Rawitz
• Computing large independent sets in a single roundDistributed Comput.
  Magnús M. Halldórsson and Christian Konrad
• Distributed Algorithms for Minimum Degree Spanning TreesarXiv
  Michael Dinitz, Magnús M. Halldórsson and Calvin Newport
• Distributed backup placement in networksDistributed Comput.
  Magnús M. Halldórsson, Sven Köhler, Boaz Patt-Shamir and Dror Rawitz
• Leveraging Indirect Signaling for Topology Inference and Fast BroadcastPODC
  Magnús M. Halldórsson and Tigran Tonoyan
• Scheduling (Dagstuhl Seminar 18101)arXiv
  Magnús M. Halldórsson, Nicole Megow and Clifford Stein
• Session details: Session 3C: ColoringPODC
  Magnús M. Halldórsson
• Simple and Local Independent Set ApproximationSIROCCO
  Ravi B. Boppana, Magnús M. Halldórsson and Dror Rawitz
• Spanning Trees With Edge Conflicts and Wireless ConnectivityICALP arXiv
  Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra and Tigran Tonoyan
• Special issue for the 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, Kyoto, JapanInf. Comput.
  Magnús M. Halldórsson, Naoki Kobayashi and Bettina Speckmann
• Wireless Aggregation at Nearly Constant RateICDCS arXiv
  Magnús M. Halldórsson and Tigran Tonoyan

2017

• Aggregation Rate for Compressible FunctionsMobiHoc
  Magnús M. Halldórsson and Tigran Tonoyan
• An Efficient Communication Abstraction for Dense Wireless NetworksDISC
  Magnús M. Halldórsson, Fabian Kuhn, Nancy A. Lynch and Calvin Newport
• Brief Announcement: Leader Election in SINR Model with Arbitrary Power ControlPODC
  Magnús M. Halldórsson, Stephan Holzer and Evangelia Anna Markatou
• Dynamic Adaptation in Wireless Networks Under Comprehensive Interference via Carrier SenseIPDPS
  Dongxiao Yu, Yuexuan Wang, Tigran Tonoyan and Magnús M. Halldórsson
• Foundations of Wireless Networking (Dagstuhl Seminar 17271)arXiv
  Christina Fragouli, Magnús M. Halldórsson, Kyle Jamieson and Bhaskar Krishnamachari
• Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring TreesSIROCCO
  Magnús M. Halldórsson and Christian Konrad
• Leader Election in SINR Model with Arbitrary Power ControlSIROCCO
  Magnús M. Halldórsson, Stephan Holzer and Evangelia Anna Markatou
• Max point-tolerance graphsDiscret. Appl. Math. arXiv
  Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halldórsson, Magnús M. Halldórsson, Thomas Hixon and Juraj Stacho
• Posimodular Function OptimizationWADS
  Magnús M. Halldórsson, Toshimasa Ishii, Kazuhisa Makino and Kenjiro Takazawa
• The Power of Oblivious Wireless PowerSIAM J. Comput.
  Magnús M. Halldórsson, Stephan Holzer, Pradipta Mitra and Roger Wattenhofer
• Universal Framework for Wireless Scheduling ProblemsICALP arXiv
  Eyjólfur Ingi Ásgeirsson, Magnús M. Halldórsson and Tigran Tonoyan
• Wireless Link Capacity under Shadowing and FadingMobiHoc arXiv
  Magnús M. Halldórsson and Tigran Tonoyan

2016

• Brief Announcement: Data Dissemination in Unified Dynamic Wireless NetworksPODC
  Magnús M. Halldórsson, Tigran Tonoyan, Yuexuan Wang and Dongxiao Yu
• Brief Announcement: Local Independent Set ApproximationPODC
  Marijke H. L. Bodlaender, Magnús M. Halldórsson, Christian Konrad and Fabian Kuhn
• Data Dissemination in Unified Dynamic Wireless NetworksarXiv
  Magnús M. Halldórsson, Tigran Tonoyan, Yuexuan Wang and Dongxiao Yu
• Invited paper: Models for wireless algorithmsWiOpt
  Magnús M. Halldórsson
• Nearly optimal bounds for distributed wireless scheduling in the SINR modelDistributed Comput. arXiv
  Magnús M. Halldórsson and Pradipta Mitra
• On the complexity of the shortest-path broadcast problemDiscret. Appl. Math.
  Pierluigi Crescenzi, Pierre Fraigniaud, Magnús M. Halldórsson, Hovhannes A. Harutyunyan, Chiara Pierucci, Andrea Pietracaprina and Geppino Pucci
• Semi-transitive orientations and word-representable graphsDiscret. Appl. Math.
  Magnús M. Halldórsson, Sergey Kitaev and Artem V. Pyatkin
• Shrinking Maxima, Decreasing Costs: New Online Packing and Covering ProblemsAlgorithmica
  Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz and Adi Rosén
• Space-Constrained Interval SelectionACM Trans. Algorithms arXiv
  Yuval Emek, Magnús M. Halldórsson and Adi Rosén
• Streaming Algorithms for Independent Sets in Sparse HypergraphsAlgorithmica
  Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja and Mario Szegedy
• The minimum vulnerability problem on specific graph classesJ. Comb. Optim.
  Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad and Xiao Zhou

2015

• A Local Broadcast Layer for the SINR Network ModelPODC arXiv
  Magnús M. Halldórsson, Stephan Holzer and Nancy A. Lynch
• Distributed Approximation of k-Service AssignmentOPODIS
  Magnús M. Halldórsson, Sven Köhler and Dror Rawitz
• Distributed Backup Placement in NetworksSPAA
  Magnús M. Halldórsson, Sven Köhler, Boaz Patt-Shamir and Dror Rawitz
• Distributed Large Independent Sets in One Round on Bounded-Independence GraphsDISC
  Magnús M. Halldórsson and Christian Konrad
• Guest editorial: Structural Information and Communication ComplexityTheor. Comput. Sci.
  Magnús M. Halldórsson
• How Well Can Graphs Represent Wireless Interference?STOC arXiv
  Magnús M. Halldórsson and Tigran Tonoyan
• Leveraging Multiple Channels in Ad Hoc NetworksPODC
  Magnús M. Halldórsson, Yuexuan Wang and Dongxiao Yu
• Limitations of Current Wireless Scheduling AlgorithmsALGOSENSORS
  Magnús M. Halldórsson, Christian Konrad and Tigran Tonoyan
• Progress (and Lack Thereof) for Graph Coloring Approximation ProblemsSOFSEM
  Magnús M. Halldórsson
• Radio Aggregation SchedulingALGOSENSORS
  Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz and Hoon Oh
• The Price of Local Power Control in Wireless SchedulingFSTTCS arXiv
  Magnús M. Halldórsson and Tigran Tonoyan
• Vertex coloring edge-weighted digraphsInf. Process. Lett.
  Jørgen Bang-Jensen and Magnús M. Halldórsson

2014

• Algorithms for Wireless CapacityIEEE/ACM Trans. Netw. arXiv
  Olga Goussevskaia, Magnús M. Halldórsson and Roger Wattenhofer
• Beyond geometry: towards fully realistic wireless modelsPODC arXiv
  Marijke H. L. Bodlaender and Magnús M. Halldórsson
• Distributed Algorithms for Coloring Interval GraphsDISC
  Magnús M. Halldórsson and Christian Konrad
• Editorial for Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile EntitiesTheor. Comput. Sci.
  Amotz Bar-Noy, Thomas Erlebach, Magnús M. Halldórsson, Sotiris E. Nikoletseas and Pekka Orponen
• Extending wireless algorithm design to arbitrary environments via metricityMSWiM
  Helga Gudmundsdottir, Eyjólfur Ingi Ásgeirsson, Marijke H. L. Bodlaender, Joseph T. Foley, Magnús M. Halldórsson and Ymir Vigfusson
• Making wireless algorithm theory more useful: five ideas from the 2013 workshop on realistic models for algorithms in wireless networksSIGACT News
  Magnús M. Halldórsson and Calvin Newport
• Maximum MIMO Flow in wireless networks under the SINR modelWiOpt
  Eyjólfur Ingi Ásgeirsson, Magnús M. Halldórsson and Pradipta Mitra
• Measurement Based Interference Models for Wireless Scheduling AlgorithmsarXiv
  Helga Gudmundsdottir, Eyjólfur Ingi Ásgeirsson, Marijke H. L. Bodlaender, Joseph T. Foley, Magnús M. Halldórsson, Geir M. Järvelä, Henning Úlfarsson and Ymir Vigfusson
• Report on Two events at ICE-TCS, Reykjavik UniversityBull. EATCS
  Luca Aceto, Magnús M. Halldórsson and Anna Ingólfsdóttir
• The Minimum Vulnerability Problem on GraphsCOCOA
  Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad and Xiao Zhou
• Wireless capacity with arbitrary gain matrixTheor. Comput. Sci. arXiv
  Magnús M. Halldórsson and Pradipta Mitra

2013

• Approximation and parameterized algorithms for common subtrees and edit distance between unordered treesTheor. Comput. Sci.
  Tatsuya Akutsu, Daiji Fukagawa, Magnús M. Halldórsson, Atsuhiro Takasu and Keisuke Tanaka
• Brief announcement: locality in wireless schedulingSPAA
  Magnús M. Halldórsson
• Connectivity and aggregation in multihop wireless networksPODC
  Marijke H. L. Bodlaender, Magnús M. Halldórsson and Pradipta Mitra
• Corrigendum: Improved results for data migration and open shop schedulingACM Trans. Algorithms
  Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz and Hadas Shachnai
• EditorialAlgorithmica
  Camil Demetrescu and Magnús M. Halldórsson
• Modeling Reality Algorithmically: The Case of Wireless CommunicationALGOSENSORS
  Magnús M. Halldórsson
• Online Scheduling with Interval ConflictsTheory Comput. Syst.
  Magnús M. Halldórsson, Boaz Patt-Shamir and Dror Rawitz
• Online selection of intervals and t-intervalsInf. Comput.
  Unnar Th. Bachmann, Magnús M. Halldórsson and Hadas Shachnai
• SDP-based algorithms for maximum independent set problems on hypergraphsTheor. Comput. Sci.
  Geir Agnarsson, Magnús M. Halldórsson and Elena Losievskaja
• Shrinking Maxima, Decreasing Costs: New Online Packing and Covering ProblemsAPPROX-RANDOM
  Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz and Adi Rosén
• The Power of Non-Uniform Wireless PowerSODA arXiv
  Magnús M. Halldórsson, Stephan Holzer, Pradipta Mitra and Roger Wattenhofer

2012

• A fully distributed algorithm for throughput performance in wireless networksCISS arXiv
  Eyjolfur Ingi Asgeirsson, Magnús M. Halldórsson and Pradipta Mitra
• Brief announcement: distributed algorithms for throughput performance in wireless networksPODC
  Eyjolfur Ingi Asgeirsson, Magnús M. Halldórsson and Pradipta Mitra
• Distributed connectivity of wireless networksPODC arXiv
  Magnús M. Halldórsson and Pradipta Mitra
• On the Impact of Identifiers on Local DecisionOPODIS arXiv
  Pierre Fraigniaud, Magnús M. Halldórsson and Amos Korman
• Online Set PackingSIAM J. Comput.
  Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan and Dror Rawitz
• Space-Constrained Interval SelectionICALP (1)
  Yuval Emek, Magnús M. Halldórsson and Adi Rosén
• Streaming and Communication Complexity of Clique ApproximationICALP (1)
  Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy and Chengu Wang
• Towards tight bounds for local broadcastingFOMC arXiv
  Magnús M. Halldórsson and Pradipta Mitra
• Wireless Network Stability in the SINR ModelSIROCCO arXiv
  Eyjolfur Ingi Asgeirsson, Magnús M. Halldórsson and Pradipta Mitra
• Wireless capacity and admission control in cognitive radioINFOCOM
  Magnús M. Halldórsson and Pradipta Mitra
• Wireless connectivity and capacitySODA arXiv
  Magnús M. Halldórsson and Pradipta Mitra
• Wireless scheduling with power controlACM Trans. Algorithms arXiv
  Magnús M. Halldórsson

2011

• Algorithms for Weighted Capacity and Admission Control in Wireless NetworksarXiv
  Magnús M. Halldórsson and Pradipta Mitra
• Alternation GraphsWG
  Magnús M. Halldórsson, Sergey Kitaev and Artem V. Pyatkin
• Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR ModelICALP (2)
  Magnús M. Halldórsson and Pradipta Mitra
• Online Scheduling with Interval ConflictsSTACS
  Magnús M. Halldórsson, Boaz Patt-Shamir and Dror Rawitz
• Sum edge coloring of multigraphs via configuration LPACM Trans. Algorithms
  Magnús M. Halldórsson, Guy Kortsarz and Maxim Sviridenko
• Wireless Capacity with Arbitrary Gain MatrixALGOSENSORS
  Magnús M. Halldórsson and Pradipta Mitra
• Wireless Capacity with Oblivious Power in General MetricsSODA arXiv
  Magnús M. Halldórsson and Pradipta Mitra

2010

• Graphs Capturing Alternations in WordsDevelopments in Language Theory
  Magnús M. Halldórsson, Sergey Kitaev and Artem V. Pyatkin
• On spectrum sharing gamesDistributed Comput.
  Magnús M. Halldórsson, Joseph Y. Halpern, Li Erran Li and Vahab S. Mirrokni
• Online Selection of Intervals and SWAT
  Unnar Th. Bachmann, Magnús M. Halldórsson and Hadas Shachnai
• Online coloring of hypergraphsInf. Process. Lett.
  Magnús M. Halldórsson
• Online set packing and competitive scheduling of multi-part tasksPODC
  Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan and Dror Rawitz
• Return of the Boss Problem: Competing Online against a Non-adaptive AdversaryFUN
  Magnús M. Halldórsson and Hadas Shachnai
• Streaming Algorithms for Independent SetsICALP (1)
  Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja and Mario Szegedy
• Vertex coloring the square of outerplanar graphs of low degreeDiscuss. Math. Graph Theory
  Geir Agnarsson and Magnús M. Halldórsson

2009

• Approximation algorithms for the weighted independent set problem in sparse graphsDiscret. Appl. Math.
  Akihisa Kako, Takao Ono, Tomio Hirata and Magnús M. Halldórsson
• Capacity of Arbitrary Wireless NetworksINFOCOM
  Olga Goussevskaia, Roger Wattenhofer, Magnús M. Halldórsson and Emo Welzl
• Independent sets in bounded-degree hypergraphsDiscret. Appl. Math.
  Magnús M. Halldórsson and Elena Losievskaja
• SDP-Based Algorithms for Maximum Independent Set Problems on HypergraphsICALP (1)
  Geir Agnarsson, Magnús M. Halldórsson and Elena Losievskaja
• Scheduling with conflicts: online and offline algorithmsJ. Sched.
  Guy Even, Magnús M. Halldórsson, Lotem Kaplan and Dana Ron
• Weighted Sum Coloring in Batch Scheduling of Conflicting JobsAlgorithmica
  Leah Epstein, Magnús M. Halldórsson, Asaf Levin and Hadas Shachnai
• Wireless Communication Is in APXICALP (1)
  Magnús M. Halldórsson and Roger Wattenhofer
• Wireless Scheduling with Power ControlESA
  Magnús M. Halldórsson

2008

• Batch Coloring Flat Graphs and ThinSWAT
  Magnús M. Halldórsson and Hadas Shachnai
• Improved bounds for scheduling conflicting jobs with minsum criteriaACM Trans. Algorithms
  Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz and Hadas Shachnai
• Min Sum Edge Coloring in Multigraphs Via Configuration LPIPCO
  Magnús M. Halldórsson, Guy Kortsarz and Maxim Sviridenko
• Minimizing interference of a wireless ad-hoc network in a planeTheor. Comput. Sci.
  Magnús M. Halldórsson and Takeshi Tokuyama
• Robust cost coloringsSODA
  Takuro Fukunaga, Magnús M. Halldórsson and Hiroshi Nagamochi
• Vertex coloring acyclic digraphs and their corresponding hypergraphsDiscret. Appl. Math.
  Geir Agnarsson, Ágúst S. Egilsson and Magnús M. Halldórsson

2007

• "Rent-or-Buy" Scheduling and Cost Coloring ProblemsFSTTCS
  Takuro Fukunaga, Magnús M. Halldórsson and Hiroshi Nagamochi
• Complete partitions of graphsComb.
  Magnús M. Halldórsson, Guy Kortsarz, Jaikumar Radhakrishnan and Sivaramakrishnan Sivasubramanian
• Fixed-Parameter Tractability for Non-Crossing Spanning TreesWADS
  Magnús M. Halldórsson, Christian Knauer, Andreas Spillner and Takeshi Tokuyama
• Improved approximation results for the stable marriage problemACM Trans. Algorithms
  Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa
• Independent Sets in Bounded-Degree HypergraphsWADS
  Magnús M. Halldórsson and Elena Losievskaja
• Strongly simplicial vertices of powers of treesDiscret. Math.
  Geir Agnarsson and Magnús M. Halldórsson

2006

• Improved results for data migration and open shop schedulingACM Trans. Algorithms
  Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz and Hadas Shachnai
• Minimizing Interference of a Wireless Ad-Hoc Network in a PlaneALGOSENSORS
  Magnús M. Halldórsson and Takeshi Tokuyama
• Scheduling Split IntervalsSIAM J. Comput.
  Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai and Irina Shapira
• Strip Graphs: Recognition and SchedulingWG
  Magnús M. Halldórsson and Ragnar K. Karlsson
• Weighted Sum Coloring in Batch Scheduling of Conflicting JobsAPPROX-RANDOM
  Leah Epstein, Magnús M. Halldórsson, Asaf Levin and Hadas Shachnai

2005

• Approximation Algorithms for the Weighted Independent Set ProblemWG
  Akihisa Kako, Takao Ono, Tomio Hirata and Magnús M. Halldórsson
• Approximation algorithms for optimization problems in graphs with superlogarithmic treewidthInf. Process. Lett.
  Artur Czumaj, Magnús M. Halldórsson, Andrzej Lingas and Johan Nilsson

2004

• Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum CriteriaWAOA
  Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz and Hadas Shachnai
• Improved Results for Data Migration and Open Shop SchedulingICALP
  Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz and Hadas Shachnai
• Multicoloring: Problems and TechniquesMFCS
  Magnús M. Halldórsson and Guy Kortsarz
• On colorings of squares of outerplanar graphsSODA
  Geir Agnarsson and Magnús M. Halldórsson
• On spectrum sharing gamesPODC
  Magnús M. Halldórsson, Joseph Y. Halpern, Li (Erran) Li and Vahab S. Mirrokni
• Randomized approximation of the stable marriage problemTheor. Comput. Sci.
  Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa
• Strong Colorings of HypergraphsWAOA
  Geir Agnarsson and Magnús M. Halldórsson

2003

• Approximability results for stable marriage problems with tiesTheor. Comput. Sci.
  Magnús M. Halldórsson, Robert W. Irving, Kazuo Iwama, David F. Manlove, Shuichi Miyazaki, Yasufumi Morita and Sandy Scott
• Approximation algorithms for the test cover problemMath. Program.
  Koen M. J. De Bontridder, Bjarni V. Halldórsson, Magnús M. Halldórsson, Cor A. J. Hurkens, Jan Karel Lenstra, R. Ravi and Leen Stougie
• Coloring Powers of Planar GraphsSIAM J. Discret. Math.
  Geir Agnarsson and Magnús M. Halldórsson
• Improved Approximation of the Stable Marriage ProblemESA
  Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa
• Multicoloring treesInf. Comput.
  Magnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai and Jan Arne Telle
• Powers of geometric intersection graphs and dispersion algorithmsDiscret. Appl. Math.
  Geir Agnarsson, Peter Damaschke and Magnús M. Halldórsson
• Proper Down-Coloring Simple Acyclic DigraphsAGTIVE
  Geir Agnarsson, Ágúst S. Egilsson and Magnús M. Halldórsson
• Randomized Approximation of the Stable Marriage ProblemCOCOON
  Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa
• Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent JobsAlgorithmica
  Magnús M. Halldórsson, Guy Kortsarz and Hadas Shachnai

2002

• Approximating the Domatic NumberSIAM J. Comput.
  Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz and Aravind Srinivasan
• Inapproximability Results on Stable Marriage ProblemsLATIN
  Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita
• Online independent setsTheor. Comput. Sci.
  Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi
• Powers of Geometric Intersection Graphs and Dispersion AlgorithmsSWAT
  Geir Agnarsson, Peter Damaschke and Magnús M. Halldórsson
• Scheduling split intervalsSODA
  Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai and Irina Shapira
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-TreesJ. Algorithms
  Magnús M. Halldórsson and Guy Kortsarz

2001

• Approximation Algorithms for Dispersion ProblemsJ. Algorithms
  Barun Chandra and Magnús M. Halldórsson
• Approximations for the general block distribution of a matrixTheor. Comput. Sci.
  Bengt Aspvall, Magnús M. Halldórsson and Fredrik Manne
• Greedy Local Improvement and Weighted Set Packing ApproximationJ. Algorithms
  Barun Chandra and Magnús M. Halldórsson
• Logical Form Equivalence: the Case of Referring Expressions GenerationEWNLG@ACL
  Kees van Deemter and Magnús M. Halldórsson
• Minimizing Average Completion of Dedicated Tasks and Interval GraphsRANDOM-APPROX
  Magnús M. Halldórsson, Guy Kortsarz and Hadas Shachnai
• On the Approximability of the Minimum Test Collection ProblemESA
  Bjarni V. Halldórsson, Magnús M. Halldórsson and R. Ravi

2000

• Approximating the domatic numberSTOC
  Uriel Feige, Magnús M. Halldórsson and Guy Kortsarz
• Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial CircuitsISAAC
  Takao Asano, Magnús M. Halldórsson, Kazuo Iwama and Takeshi Matsuda
• Approximations of Weighted Independent Set and Hereditary Subset ProblemsJ. Graph Algorithms Appl.
  Magnús M. Halldórsson
• Coloring powers of planar graphsSODA
  Geir Agnarsson and Magnús M. Halldórsson
• Guest Editor's ForewordNord. J. Comput.
  Magnús M. Halldórsson
• Independent Sets with Domination ConstraintsDiscret. Appl. Math.
  Magnús M. Halldórsson, Jan Kratochvíl and Jan Arne Telle
• Mod-2 Independence and Domination in GraphsInt. J. Found. Comput. Sci.
  Magnús M. Halldórsson, Jan Kratochvíl and Jan Arne Telle
• On the approximation of largest common subtrees and largest common point setsTheor. Comput. Sci.
  Tatsuya Akutsu and Magnús M. Halldórsson
• Online Coloring Known GraphsElectron. J. Comb.
  Magnús M. Halldórsson
• Online Independent SetsCOCOON
  Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi
• Sum Multicoloring of GraphsJ. Algorithms
  Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz, Ravit Salman and Hadas Shachnai

1999

• A Matched Approximation Bound for the Sum of a Greedy ColoringInf. Process. Lett.
  Amotz Bar-Noy, Magnús M. Halldórsson and Guy Kortsarz
• Approximations of Weighted Independent Set and Hereditary Subset ProblemsCOCOON
  Magnús M. Halldórsson
• Finding Subsets Maximizing Minimum StructuresSIAM J. Discret. Math.
  Magnús M. Halldórsson, Kazuo Iwano, Naoki Katoh and Takeshi Tokuyama
• Greedy Local Improvement and Weighted Set Packing ApproximationSODA
  Barun Chandra and Magnús M. Halldórsson
• Mod-2 Independence and Domination in GraphsWG
  Magnús M. Halldórsson, Jan Kratochvíl and Jan Arne Telle
• Multi-coloring TreesCOCOON
  Magnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai and Jan Arne Telle
• Multicoloring Planar Graphs and Partial k-TreesRANDOM-APPROX
  Magnús M. Halldórsson and Guy Kortsarz
• Online Coloring Known GraphsSODA
  Magnús M. Halldórsson
• Sum Multi-coloring of GraphsESA
  Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz, Ravit Salman and Hadas Shachnai

1998

• Approximating Steiner trees in graphs with restricted weightsNetworks
  Magnús M. Halldórsson, Shuichi Ueno, Hiroshi Nakao and Yoji Kajitani
• Approximations for the General Block Distribution of a MatrixSWAT
  Bengt Aspvall, Magnús M. Halldórsson and Fredrik Manne
• Approximations of Independent Sets in GraphsAPPROX
  Magnús M. Halldórsson
• Independent Sets with Domination ConstraintsICALP
  Magnús M. Halldórsson, Jan Kratochvíl and Jan Arne Telle
• On Chromatic Sums and Distributed Resource AllocationInf. Comput.
  Amotz Bar-Noy, Mihir Bellare, Magnús M. Halldórsson, Hadas Shachnai and Tami Tamir

1997

• Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree GraphsAlgorithmica
  Magnús M. Halldórsson and Jaikumar Radhakrishnan
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and ColoringJ. Graph Algorithms Appl.
  Magnús M. Halldórsson and Hoong Chuin Lau
• Parallel and On-Line Graph ColoringJ. Algorithms
  Magnús M. Halldórsson

1996

• Approximating IPCO
  Magnús M. Halldórsson
• Approximation and Special Cases of Common Subtrees and Editing DistanceISAAC
  Magnús M. Halldórsson and Keisuke Tanaka
• Facility Dispersion and Remote SubgraphsSWAT
  Barun Chandra and Magnús M. Halldórsson

1995

• Approximating Discrete Collections via Local ImprovementsSODA
  Magnús M. Halldórsson
• Finding Subsets Maximizing Minimum StructuresSODA
  Magnús M. Halldórsson, Kazuo Iwano, Naoki Katoh and Takeshi Tokuyama
• Greedy Approximations of Independent Sets in Low Degree GraphsISAAC
  Magnús M. Halldórsson and Kiyohito Yoshihara

1994

• Greed is good: approximating independent sets in sparse and bounded-degree graphsSTOC
  Magnús M. Halldórsson and Jaikumar Radhakrishnan
• Improved Approximations of Independent Sets in Bounded-Degree GraphsSWAT
  Magnús M. Halldórsson and Jaikumar Radhakrishnan
• Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph RemovalNord. J. Comput.
  Magnús M. Halldórsson and Jaikumar Radhakrishnan
• Lower Bounds for On-Line Graph ColoringTheor. Comput. Sci.
  Magnús M. Halldórsson and Mario Szegedy
• On the Approximation of Largest Common Subtrees and Largest Common Point SetsISAAC
  Tatsuya Akutsu and Magnús M. Halldórsson

1993

• A Still Better Performance Guarantee for Approximate Graph ColoringInf. Process. Lett.
  Magnús M. Halldórsson
• Approximating the Minimum Maximal Independence NumberInf. Process. Lett.
  Magnús M. Halldórsson
• Approximating the Tree and Tour Covers of a GraphInf. Process. Lett.
  Esther M. Arkin, Magnús M. Halldórsson and Refael Hassin
• Directed vs. Undirected Monotone Contact Networks for Threshold FunctionsFOCS
  Magnús M. Halldórsson, Jaikumar Radhakrishnan and K. V. Subrahmanyam
• On Some Communication Complexity Problems Related to THreshold FunctionsFSTTCS
  Magnús M. Halldórsson, Jaikumar Radhakrishnan and K. V. Subrahmanyam

1992

• Approximating Maximum Independent Sets by Excluding SubgraphsBIT
  Ravi B. Boppana and Magnús M. Halldórsson
• Lower Bounds for On-Line Graph ColoringSODA
  Magnús M. Halldórsson and Mario Szegedy
• Parallel and On-line Graph Coloring AlgorithmsISAAC
  Magnús M. Halldórsson

1991

• Lower Bounds for On-line Graph ColoringOn-Line Algorithms
  Magnús M. Halldórsson and Mario Szegedy

1990

• Approximating Maximum Independent Sets by Excluding SubgraphsSWAT
  Ravi B. Boppana and Magnús M. Halldórsson