Magnus M. Halldorsson: Online papers
For work on wireless algorithms, see here.
Most of my recent papers are on arXiv.
The following works are the last versions leaving my hands. They may
not incorporate corrections made in galley proofs or copyediting.
Copyright rests with the respective publisher.
Distributed Large Independent Sets in a Single Round
Distributed Computing (with Christian Konrad), published online March 2017.
Max Point-Tolerance Graphs.
(with Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halld\'orsson, Thomas Hixon, Juraj Stacho)
Discrete Applied Mathematics 216(1):84--97, January 2017.
- Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems (with Pierre Fraigniaud, Boaz Patt-Shamir, Dror Rawitz, Adi Rosen)
Algorithmica 74(4): 1205-1223, 2016.
- On the complexity of the shortest-path broadcast problem (with Pierluigi Crescenzi, Pierre Fraigniaud, Hovhannes A. Harutyunyan, Chiara Pierucci, Andrea Pietracaprina, Geppino Pucci).
Discrete Applied Mathematics 199: 101-109, 2016.
Semi-Transitive Orientations and Word-Representable Graphs
(with Sergey Kitaev, Artem Pyatkin).
Discrete Applied Math 201:164-171, 2016.
(This version: arXiv:1501.07108 [math.CO], January 2015.)
(Full (and corrected) version of WG'10 paper)
- Streaming Algorithms for Independent Sets
Algorithmica, 2016 (with Bjarni V. Halldorsson, Elena Losievskja and Mario Szegedy).
A Note on Vertex Coloring Edge-Weighted Digraphs (with Joergen Bang-Jensen)
Mittag-Leffler Report No. 29, 2013/2014, spring.
Information Processing Letters, 115(10):791-796, October 2015.
Online selection of intervals and t-intervals.
Information and Computation 233:1-11, December 2013
(with Unnar Th. Bachmann and Hadas Shachnai)
- Scheduling with interval conflicts
Theory of Computing Systems 53(2):300-317, August 2013;
earlier version appeared in STACS '11 (with Boaz Patt-Shamir, Dror Rawitz).
Approximation and Special Cases of Common Subtrees and Editing Distance.
Theoretical Computer Science, Jan 2013 (with Tatsyua Akutsu,
Daiji Fukagawa, Atsuhiro Takasu, and Keisuke Tanaka).
- SDP-based Algorithms for Maximum
Independent Set Problems on Hypergraphs.
Theoretical Computer Science, Jan 2013 (with Geir Agnarsson and Elena Losievskaja).
- Online set packing and competitive
scheduling of multi-part tasks.
SICOMP, 41(4):728-746, 2012.
(Earlier version appeared in PODC'10). (With
Yuval Emek, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan and Dror Rawitz).
Vertex coloring the square of outerplanar graphs of low degree.
Discussiones Mathematicae Graph Theory 30(4):619--636, 2010.
(with Geir Agnarsson).
Online coloring of hypergraphs.
Information Processing Letters 110:370--372, 2010.
Approximating Independent Sets in Bounded-Degree Hypergraphs.
Discrete Applied Mathematics 157 (2009) 1773--1786, 2009
(with Elena Losievskaja).
Approximation algorithms for the weighted independent set problem in sparse graphs.
Discrete Applied Mathematics, April 2009
(with Akihisa Kako, Takao Ono, and Tomio Hirata)
Scheduling with conflicts: Online and offline algorithms.
Journal of Scheduling, April 2009
(with Guy Even, Lotem Kaplan, and Dana Ron)
Sum Coloring in Batch Scheduling of Conflicting Jobs.
Algorithmica, Dec 2009
(with Leah Epstein, Asaf Levin, Hadas Shachnai)
Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
Theoretical Computer Science, 2008
(with Takeshi Tokuyama)
- Complete Partitions of Graphs.
(with Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian.)
Vertex coloring acyclic digraphs and their corresponding hypergraphs.
Discrete Applied Mathematics, 2007.
(with Geir Agnarsson and Agust Egilsson.)
- Strongly Simplicial Vertices of Powers of Trees
Discrete Mathematics, 2007
(with Geir Agnarsson.)
- Scheduling Split Interval Graphs.
SIAM Journal of Computing, Vol. 36, No. 1, 1--15, 2006
(with Reuven Bar-Yehuda, Seffi Naor, Hadas Shachnai, and Irina Shapira.)
Approximating the $(h,k)$-labelling problem.
Int. J. Mobile Mobile Network Design and Innovation 1(2):113--117, 2006.
Approximation algorithms for optimization problems in graphs with
Information Processing Letters 94(2):49-53, 2005
(with Artur Czumaj, Andrzej Lingas, and Johan Nilsson.)
- Randomized approximation of the stable marriage problem.
Theoretical Computer Science 325(3):439-465, 2004
(with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa.)
- Powers of Geometric Intersection Graphs
and Dispersion Algorithms
Discrete Applied Mathematics, 2003
(with Geir Agnarsson, Peter Damaschke.)
- Coloring Squares of Graphs.
SIAM J. Discrete Math, 2003
(with Geir Agnarsson.)
- Sum Coloring Interval and k-Claw Free Graphs
with Application to Scheduling Dependent Jobs.
(with Guy Kortsarz and Hadas Shachnai.)
- Approximation algorithms for the
minimum test set problem.
Mathematical Programming-B, 2003
(with Koen M.J. De Bontridder, Bjarni V. Halldórsson, Cor A.J. Hurkens, Jan K. Lenstra, R. Ravi, and Leen
- Approximability results for the
stable marriage problem with ties.
Theoretical Computer Science, 2003
(with Robert W. Irving, Kazuo Iwama, David F. Manlove, Shuichi
Miyazaki, Yasufumi Morita, and Sandy Scott.)
- Tools for Multicoloring with
Applications to Planar Graphs and Partial k-Trees.
Journal of Algorithms, 42(2), 334-366, February 2002
(with Guy Kortsarz.)
- Online Independent Sets.
Theoretical Computer Science, 289(2), 953--962, October 2002
(with Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi.)
- Approximating the domatic number.
SIAM Journal of Computing 32(1), 172--195, December 2002
(with Uriel Feige, Guy Kortsarz, and Arvind Srinivasan.)
- Multicoloring Trees.
Information and Computation, Available online 12 December 2002
(with Guy Kortsarz, Andrzej Proskurowski,
Ravit Salman, Hadas Shachnai, and Jan Arne Telle)
Approximations for the Generalized Block Distribution of a Matrix.
Theoretical Computer Science 262(1-2), 145--160, July 2001
(with Bengt Aspvall and Fredrik Manne.),
Online coloring known graphs.
Electronic J. of Combinatorics Feb 2000.
- Mod-2 Independence and Domination in Graphs.
Discrete Applied Math.
Earlier version appears in WG '99, LNCS.
(with Jan Kratochvil, Jan Arne Telle.)
Sum Multicoloring of Graphs.
Journal of Algorithms, Mar 2000.
Extended abstract appears in ESA '99.
(with Amotz Bar-Noy, Guy Kortsarz, Hadas Shachnai, Ravit Salman),
Approximations of Weighted Independent Set and Hereditary Subset
Journal of Graphs Algorithms and Applications,
Vol.4, No.1, pp.1-16.
Algorithms for Dispersion Problems.
Journal of Algorithms, April 2000 (with Barun Chandra.)
- Powers of
chordal graphs and their coloring.
Congressus Numerantium, (since Sept 2000)
(with Geir Agnarsson, Ray Greenlaw)
- Greedy local improvement and weighted set packing approximation.
Journal of Algorithms, 39(2), 223-240, May 2000.
(with Barun Chandra)
- A matched approximation bound for the sum of a greedy coloring.
Information Processing Letters 71, 135-140, 1999.
(with Amotz Bar-Noy and Guy Kortsarz)
Finding Subsets Maximizing Minimum Structures.
SIAM Journal of Discrete Math 12(3), 342-359, 1999.
(with Kazuo Iwano, Naoki Katoh, and Takeshi Tokuyama.),
- On the approximation of largest common point
sets and largest common subtrees.
Theoretical Computer Science 233(1-2), 33-50, 17 Dec 1999.
(with Tatsuya Akutsu),
Independent sets with domination constraints.
Discrete Applied Mathematics, 99(1-3), 39-54, 17 Dec 1999.
(with Jan Kratochvíl, Jan Arne Telle.),
On Chromatic Sums and Distributed Resource Allocation.
Information and Computation 140(2), February 1998
(with Amotz Bar-Noy, Mihir Bellare, Hadas Shachnai, and Tami Tamir)
Approximating Steiner trees in graphs with restricted weights.
Networks 31(4):283-292, 1998.
(with Shuichi Ueno, Hiroshi Nakao, and Yoji Kajitani.),
Greed is good: Approximating independent sets in sparse and
Algorithmica 18:143-163 (1997), special issue on on approximation
algorithms. (with Jaikumar Radhakrishnan.)
Parallel and online graph coloring.
Journal of Algorithms, 23:265-280 (1997),
Low-degree Graph Partitioning via Local Search with Applications to
Constraint Satisfaction, Max Cut, and Coloring.
Journal of Graph Algorithms and Applications 1(3):1--13, Nov. 1997 (with Hoong-Chuin Lau.) (See also here)
Lower bounds for on-line graph coloring.
Theoretical Computer Science 130:163--174, August 1994.
(with Mario Szegedy),
Improved approximations of bounded-degree independent sets via
In a special issue of Nordic J. Computing, 1(4):475--492, Winter 1994.
(with Jaikumar Radhakrishnan.), PDF
Received the Carl-Erik Fröberg Prize for a young Nordic author
of a distinguished paper published in
the Nordic Journal of
Computing in 1994-1996.
A still better performance guarantee for approximate graph
Information Processing Letters, 45:19--23, 25 January 1993,
Approximating the minimum maximal independence number.
Information Processing Letters, 46:169--172, 25 June 1993.
Approximating the tree and tour covers of a graph.
Information Processing Letters, 47:275--282, 18 October 1993
(with Estie Arkin and Rafi Hassin),
Approximating maximum independent sets by excluding subgraphs.
BIT, 32(2):180--196, June 1992 (with Ravi B. Boppana),
Refereed Conference Publications
The following are primarily papers that have not been superseded by later versions.
For superseded papers, see here.
Distributed Approximation of k-Service Assignment
OPODIS'15. LIPcs vol. 46, 2016. (with Sven Köhler, Dror Rawitz)
Distributed Large Independent Sets in One Round On Bounded-independence Graphs
DISC'15 (with Christian Konrad)
- Progress (and Lack Thereof) for Graph Coloring Approximation Problems
SOFSEM'15 (invited paper), Jan 2015
The Minimum Vulnerability Problem on Graphs
COCOA'14 (with Yusuke Aoki, Bjarni V. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou)
Distributed Algorithms for Coloring Interval Graphs,
DISC '14 (with Christian Konrad)
Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems.
APPROX'13 (with Pierre Fraigniaud, Boaz Patt-Shamir, Dror Rawitz, Adi Rosen)
On the Impact of Identifiers on Local Decision.
OPODIS'12, Dec 2012.
(with Pierre Fraigniaud, and Amos Korman)
Space-Constrained Interval Selection
ICALP '12, arXiv:1202.4326v1 (with Yuval Emek and Adi Rosen).
- Streaming Algorithms for Independent Sets
ICALP, July 2010 (with Bjarni V. Halldorsson, Elena Losievskja and
- Return of the Boss Problem: Competing Online Against a Non-Adaptive Adversary
FUN, June 2010 (with Hadas Shachnai).
Batch Coloring Tree-like Graphs
SWAT 2008 (with Hadas Shachnai).
Robust Cost Coloring
SODA 2008 (with Takuro Fukunaga and Hiroshi Nagamochi).
Rent-or-Buy scheduling and cost coloring problems
FSTTCS 2007 (with Takuro Fukunaga and Hiroshi Nagamochi).
- Parameterized algorithms and
complexity of non-crossing spanning trees.
(with Christian Knauer, Andreas Spillner, Takeshi Tokuyama).
- Strip graphs: Recognition and Scheduling.
WG '06 (with Ragnar K. Karlsson).
- Strong colorings of hypergraphs.
WAOA 2004 (with Geir Agnarsson).
- Logical form equivalence: The case of referring expressions generation.
8th European Workshop on Natural Language Generation, 2001
(with Kees van Deemter).
- On computing Prufer codes in parallel.
Journées de l'Informatique Messine -- Algorithmes de graphes,
May 2000 (with Ray Greenlaw, and Rossella Petreschi).
- Approximation Algorithms for the Maximum Power Consumption Problem
on Combinatorial Circuits.
ISAAC '00 (with Takao Asano, Kazuo Iwama, Takeshi Matsuda).
Approximating k-Set Cover and Complementary Graph Coloring.
Greedy Approximations of Independent Sets in Low Degree Graphs.
ISAAC '95 (with Kiyohito Yoshihara)
Approximating Discrete Collections via Local Improvements
- On some
communication complexity problems related to threshold functions
FSTTCS '93 (with K. V. Subrahmanyam, and Jaikumar Radhakrishnan).
- Directed vs.
undirected monotone contact networks for threshold functions.
FOCS '93(with K. V. Subrahmanyam, and Jaikumar Radhakrishnan).
- Multicoloring: Problems and Techniques.
Invited paper to MFCS '04.
of independent sets in graphs. Invited survey paper, from APPROX '98.
- A superlinear lower bound for undirected monotone contact
networks computing ...
(with K. V. Subrahmanyam, and Jaikumar Radhakrishnan)
Manuscript, September 1994.
JAIST Research Report IS-RR-95-0003F, March 1995.
(Most, but not all, of the results in the manuscript appeared later in
Papers in Icelandic
Last revised February 2015, Magnus M Halldorsson