Magnús M. Halldórsson

According to our database1, Magnús M. Halldórsson authored at least 168 papers between 1990 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Plain SINR is Enough!
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Distributed Minimum Degree Spanning Trees.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018
Special issue for the 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, Kyoto, Japan.
Inf. Comput., 2018

Computing large independent sets in a single round.
Distributed Computing, 2018

Scheduling (Dagstuhl Seminar 18101).
Dagstuhl Reports, 2018

Simple and Local Independent Set Approximation.
Proceedings of the Structural Information and Communication Complexity, 2018

Leveraging Indirect Signaling for Topology Inference and Fast Broadcast.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Session details: Session 3C: Coloring.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Brief Announcement: Simple and Local Independent Set Approximation.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Wireless Aggregation at Nearly Constant Rate.
Proceedings of the 38th IEEE International Conference on Distributed Computing Systems, 2018

Spanning Trees With Edge Conflicts and Wireless Connectivity.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
The Power of Oblivious Wireless Power.
SIAM J. Comput., 2017

Max point-tolerance graphs.
Discrete Applied Mathematics, 2017

Foundations of Wireless Networking (Dagstuhl Seminar 17271).
Dagstuhl Reports, 2017

An Efficient Communication Abstraction for Dense Wireless Networks.
Proceedings of the 31st International Symposium on Distributed Computing, 2017

Posimodular Function Optimization.
Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees.
Proceedings of the Structural Information and Communication Complexity, 2017

Leader Election in SINR Model with Arbitrary Power Control.
Proceedings of the Structural Information and Communication Complexity, 2017

Brief Announcement: Leader Election in SINR Model with Arbitrary Power Control.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Aggregation Rate for Compressible Functions.
Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2017

Wireless Link Capacity under Shadowing and Fading.
Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2017

Dynamic Adaptation in Wireless Networks Under Comprehensive Interference via Carrier Sense.
Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium, 2017

Universal Framework for Wireless Scheduling Problems.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
The minimum vulnerability problem on specific graph classes.
J. Comb. Optim., 2016

Semi-transitive orientations and word-representable graphs.
Discrete Applied Mathematics, 2016

On the complexity of the shortest-path broadcast problem.
Discrete Applied Mathematics, 2016

Streaming Algorithms for Independent Sets in Sparse Hypergraphs.
Algorithmica, 2016

Invited paper: Models for wireless algorithms.
Proceedings of the 14th International Symposium on Modeling and Optimization in Mobile, 2016

Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Brief Announcement: Local Independent Set Approximation.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015
Guest editorial: Structural Information and Communication Complexity.
Theor. Comput. Sci., 2015

Vertex coloring edge-weighted digraphs.
Inf. Process. Lett., 2015

Distributed Large Independent Sets in One Round on Bounded-Independence Graphs.
Proceedings of the Distributed Computing - 29th International Symposium, 2015

How Well Can Graphs Represent Wireless Interference?
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Distributed Backup Placement in Networks.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Progress (and Lack Thereof) for Graph Coloring Approximation Problems.
Proceedings of the SOFSEM 2015: Theory and Practice of Computer Science, 2015

Leveraging Multiple Channels in Ad Hoc Networks.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

A Local Broadcast Layer for the SINR Network Model.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Distributed Approximation of k-Service Assignment.
Proceedings of the 19th International Conference on Principles of Distributed Systems, 2015

The Price of Local Power Control in Wireless Scheduling.
Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Limitations of Current Wireless Scheduling Algorithms.
Proceedings of the Algorithms for Sensor Systems, 2015

Radio Aggregation Scheduling.
Proceedings of the Algorithms for Sensor Systems, 2015

2014
Algorithms for Wireless Capacity.
IEEE/ACM Trans. Netw., 2014

Editorial for Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities.
Theor. Comput. Sci., 2014

Making wireless algorithm theory more useful: five ideas from the 2013 workshop on realistic models for algorithms in wireless networks.
SIGACT News, 2014

Report on Two events at ICE-TCS, Reykjavik University.
Bulletin of the EATCS, 2014

Maximum MIMO Flow in wireless networks under the SINR model.
Proceedings of the 12th International Symposium on Modeling and Optimization in Mobile, 2014

Distributed Algorithms for Coloring Interval Graphs.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

Beyond geometry: towards fully realistic wireless models.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Extending wireless algorithm design to arbitrary environments via metricity.
Proceedings of the 17th ACM International Conference on Modeling, 2014

The Minimum Vulnerability Problem on Graphs.
Proceedings of the Combinatorial Optimization and Applications, 2014

2013
Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees.
Theor. Comput. Sci., 2013

Corrigendum: Improved results for data migration and open shop scheduling.
ACM Trans. Algorithms, 2013

Online selection of intervals and t-intervals.
Inf. Comput., 2013

Editorial.
Algorithmica, 2013

Brief announcement: locality in wireless scheduling.
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

The Power of Non-Uniform Wireless Power.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Connectivity and aggregation in multihop wireless networks.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

Modeling Reality Algorithmically: The Case of Wireless Communication.
Proceedings of the Algorithms for Sensor Systems, 2013

2012
Online Set Packing.
SIAM J. Comput., 2012

Wireless connectivity and capacity.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Wireless Network Stability in the SINR Model.
Proceedings of the Structural Information and Communication Complexity, 2012

Distributed connectivity of wireless networks.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Brief announcement: distributed algorithms for throughput performance in wireless networks.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

On the Impact of Identifiers on Local Decision.
Proceedings of the Principles of Distributed Systems, 16th International Conference, 2012

Wireless capacity and admission control in cognitive radio.
Proceedings of the IEEE INFOCOM 2012, Orlando, FL, USA, March 25-30, 2012, 2012

Streaming and Communication Complexity of Clique Approximation.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Space-Constrained Interval Selection.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Towards tight bounds for local broadcasting.
Proceedings of the FOMC'12, 2012

A fully distributed algorithm for throughput performance in wireless networks.
Proceedings of the 46th Annual Conference on Information Sciences and Systems, 2012

2011
Sum edge coloring of multigraphs via configuration LP.
ACM Trans. Algorithms, 2011

Alternation Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

Online Scheduling with Interval Conflicts.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Wireless Capacity with Oblivious Power in General Metrics.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Wireless Capacity with Arbitrary Gain Matrix.
Proceedings of the Algorithms for Sensor Systems, 2011

2010
Online coloring of hypergraphs.
Inf. Process. Lett., 2010

Vertex coloring the square of outerplanar graphs of low degree.
Discussiones Mathematicae Graph Theory, 2010

Online Selection of Intervals and t-Intervals.
Proceedings of the Algorithm Theory, 2010

Online set packing and competitive scheduling of multi-part tasks.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Streaming Algorithms for Independent Sets.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Return of the Boss Problem: Competing Online against a Non-adaptive Adversary.
Proceedings of the Fun with Algorithms, 5th International Conference, 2010

Graphs Capturing Alternations in Words.
Proceedings of the Developments in Language Theory, 14th International Conference, 2010

2009
Scheduling with conflicts: online and offline algorithms.
J. Scheduling, 2009

Approximation algorithms for the weighted independent set problem in sparse graphs.
Discrete Applied Mathematics, 2009

Capacity of Arbitrary Wireless Networks.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

Wireless Communication Is in APX.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Wireless Scheduling with Power Control.
Proceedings of the Algorithms, 2009

2008
Improved bounds for scheduling conflicting jobs with minsum criteria.
ACM Trans. Algorithms, 2008

Vertex coloring acyclic digraphs and their corresponding hypergraphs.
Discrete Applied Mathematics, 2008

Batch Coloring Flat Graphs and Thin.
Proceedings of the Algorithm Theory, 2008

Robust cost colorings.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Min Sum Edge Coloring in Multigraphs Via Configuration LP.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008

2007
Improved approximation results for the stable marriage problem.
ACM Trans. Algorithms, 2007

Strongly simplicial vertices of powers of trees.
Discrete Mathematics, 2007

Complete partitions of graphs.
Combinatorica, 2007

Independent Sets in Bounded-Degree Hypergraphs.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Fixed-Parameter Tractability for Non-Crossing Spanning Trees.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

"Rent-or-Buy" Scheduling and Cost Coloring Problems.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

2006
Strip Graphs: Recognition and Scheduling.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
Proceedings of the Approximation, 2006

Minimizing Interference of a Wireless Ad-Hoc Network in a Plane.
Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2006

2005
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth.
Inf. Process. Lett., 2005

Approximation Algorithms for the Weighted Independent Set Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

2004
Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Strong Colorings of Hypergraphs.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

On colorings of squares of outerplanar graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

On spectrum sharing games.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Multicoloring: Problems and Techniques.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Improved Results for Data Migration and Open Shop Scheduling.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
Approximability results for stable marriage problems with ties.
Theor. Comput. Sci., 2003

Approximation algorithms for the test cover problem.
Math. Program., 2003

Multicoloring trees.
Inf. Comput., 2003

Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.
Algorithmica, 2003

Improved Approximation of the Stable Marriage Problem.
Proceedings of the Algorithms, 2003

Randomized Approximation of the Stable Marriage Problem.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

Proper Down-Coloring Simple Acyclic Digraphs.
Proceedings of the Applications of Graph Transformations with Industrial Relevance, 2003

2002
Approximating the Domatic Number.
SIAM J. Comput., 2002

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees.
J. Algorithms, 2002

Powers of Geometric Intersection Graphs and Dispersion Algorithms.
Proceedings of the Algorithm Theory, 2002

Scheduling split intervals.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Inapproximability Results on Stable Marriage Problems.
Proceedings of the LATIN 2002: Theoretical Informatics, 2002

2001
Approximation Algorithms for Dispersion Problems.
J. Algorithms, 2001

Minimizing Average Completion of Dedicated Tasks and Interval Graphs.
Proceedings of the Approximation, 2001

On the Approximability of the Minimum Test Collection Problem.
Proceedings of the Algorithms, 2001

Logical Form Equivalence: the Case of Referring Expressions Generation.
Proceedings of the ACL 2001 Eighth European Workshop on Natural Language Generation, 2001

2000
Guest Editor's Foreword.
Nord. J. Comput., 2000

Sum Multicoloring of Graphs.
J. Algorithms, 2000

Approximating the domatic number.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Coloring powers of planar graphs.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.
Proceedings of the Algorithms and Computation, 11th International Conference, 2000

Online Independent Sets.
Proceedings of the Computing and Combinatorics, 6th Annual International Conference, 2000

1999
A Matched Approximation Bound for the Sum of a Greedy Coloring.
Inf. Process. Lett., 1999

Mod-2 Independence and Domination in Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

Online Coloring Known Graphs.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Greedy Local Improvement and Weighted Set Packing Approximation.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Multicoloring Planar Graphs and Partial k-Trees.
Proceedings of the Randomization, 1999

Sum Multi-coloring of Graphs.
Proceedings of the Algorithms, 1999

Multi-coloring Trees.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

Approximations of Weighted Independent Set and Hereditary Subset Problems.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998
Approximating Steiner trees in graphs with restricted weights.
Networks, 1998

On Chromatic Sums and Distributed Resource Allocation.
Inf. Comput., 1998

Approximations for the General Block Distribution of a Matrix.
Proceedings of the Algorithm Theory, 1998

Independent Sets with Domination Constraints.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Approximations of Independent Sets in Graphs.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997
Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring.
J. Graph Algorithms Appl., 1997

Parallel and On-Line Graph Coloring.
J. Algorithms, 1997

1996
Facility Dispersion and Remote Subgraphs.
Proceedings of the Algorithm Theory, 1996

Approximation and Special Cases of Common Subtrees and Editing Distance.
Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

Approximating k-Set Cover and Complementary Graph Coloring.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

1995
Finding Subsets Maximizing Minimum Structures.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Approximating Discrete Collections via Local Improvements.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Greedy Approximations of Independent Sets in Low Degree Graphs.
Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

1994
Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal.
Nord. J. Comput., 1994

Improved Approximations of Independent Sets in Bounded-Degree Graphs.
Proceedings of the Algorithm Theory, 1994

Greed is good: approximating independent sets in sparse and bounded-degree graphs.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On the Approximation of Largest Common Subtrees and Largest Common Point Sets.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

1993
Approximating the Minimum Maximal Independence Number.
Inf. Process. Lett., 1993

A Still Better Performance Guarantee for Approximate Graph Coloring.
Inf. Process. Lett., 1993

Approximating the Tree and Tour Covers of a Graph.
Inf. Process. Lett., 1993

On Some Communication Complexity Problems Related to THreshold Functions.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

Directed vs. Undirected Monotone Contact Networks for Threshold Functions
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Lower Bounds for On-Line Graph Coloring.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Parallel and On-line Graph Coloring Algorithms.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

1991
Lower Bounds for On-line Graph Coloring.
Proceedings of the On-Line Algorithms, 1991

1990
Approximating Maximum Independent Sets by Excluding Subgraphs.
Proceedings of the SWAT 90, 1990


  Loading...