Online papers

Refereed Conference Publications

  1. Wireless scheduling with power control
    ESA '09.
  2. SDP-based Algorithms for Maximum Independent Set Problems on Hypergraphs.
    ICALP, July 2009 (with Geir Agnarsson and Elena Losievskaja).
  3. Wireless Communication is in APX
    ICALP, July 2009 (with Roger Wattenhofer).
  4. Capacity of Arbitrary Wireless Networks
    INFOCOM, April 2009 (with Olga Goussevskaia, Roger Wattenhofer, and Emo Welzl).
  5. Batch Coloring Tree-like Graphs
    SWAT 2008 (with Hadas Shachnai).
  6. Min Sum Edge Coloring in Multigraphs via Configuration LP.
    IPCO 2008 (with Guy Kortsarz and Maxim Sviridenko).
  7. Robust Cost Coloring
    SODA 2008 (with Takuro Fukunaga and Hiroshi Nagamochi).
  8. Rent-or-Buy scheduling and cost coloring problems
    FSTTCS 2007 (with Takuro Fukunaga and Hiroshi Nagamochi).
  9. Approximating Independent Sets in Bounded-Degree Hypergraphs.
    WADS '07 (with Elena Losievskaja). (See journal version below)
  10. Parameterized algorithms and complexity of non-crossing spanning trees.
    WADS '07 (with Christian Knauer, Andreas Spillner, Takeshi Tokuyama).
  11. Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
    ALGOSENSORS '06 (with Takeshi Tokuyama).
  12. Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
    APPROX '06 (with Leah Epstein, Asaf Levin, Hadas Shachnai).
  13. Strip graphs: Recognition and Scheduling.
    WG '06 (with Ragnar K. Karlsson).
  14. Approximation Algorithms for the Weighted Independent Set Problem.
    WG ’05(with Akihisa Kako, Takao Ono, Tomio Hirata)
  15. Strong colorings of hypergraphs.
    WAOA 2004 (with Geir Agnarsson).
  16. Improved Bounds for Sum Multicoloring and Weighted Completion Time of Dependent Jobs
    WAOA 2004 (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai).
  17. On Spectrum Sharing Games
    PODC 2004 (with Joseph Y. Halpern, Li (Erran) Li, Vahab S. Mirrokni) (pdf)
  18. Improved results for data migration and open-shop scheduling. ICALP 2004 (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai).
  19. On Coloring Squares of Outerplanar graphs.
    SODA 2004 (with Geir Agnarsson).
  20. Proper down-coloring of simple acyclic digraphs.
    Proceedings of Applications of Graph Transformations with Industrial Relevance – Second International Workshop, AGTIVE 2003, Charlottesville, VA, USA, September 27 - October 1, 2003, LNCS #3062, May 2004. (with Geir Agnarsson, Ágúst Egilsson)
  21. Improved approximation of the stable marriage problem.
    ESA 2003 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa).
  22. Randomized approximation of the stable marriage problem.
    COCOON 2003 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa)
  23. Powers of Geometric Intersection Graphs and Dispersion Algorithms.
    SWAT 2002 (with Geir Agnarsson, Peter Damaschke)
  24. Inapproximability Results on Stable Marriage Problems  (with Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita)
    LATIN 2002.
  25. Scheduling Split Interval Graphs.
    (with Reuven Bar-Yehuda, Seffi Naor, Hadas Shachnai, and Irina Shapira)
    SODA 2002
  26. Logical form equivalence: The case of referring expressions generation. (with Kees van Deemter)
    8th European Workshop on Natural Language Generation, 2001.
  27. On the approximability of the minimum test collection problem. (with Bjarni V. Halldórsson  and R. Ravi)
    ESA 2001
  28. Minimizing Average Completion of Dedicated Tasks and Interval Graphs. (with Guy Kortsarz and Hadas. Shachnai)
    APPROX 2001
  29. Approximating the domatic number.
     STOC 2000 (with Uriel Feige, Guy Kortsarz)
    [© 2000 ACM Inc., included here by permission]
  30. On computing Prufer codes in parallel.
    Journées de l'Informatique Messine -- Algorithmes de graphes, May 2000 (with Ray Greenlaw, and Rossella Petreschi).
  31. Online Independent Sets.
    COCOON '00 (with Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi).
  32. Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.
    ISAAC '00 (with Takao Asano, Kazuo Iwama, Takeshi Matsuda).
  33. Sum Multicoloring of Graphs.
    ESA '99 (with Amotz Bar-Noy, Guy Kortsarz, Hadas Shachnai, Ravit Salman).
  34. Approximations of Weighted Independent Set and Hereditary Subset Problems. 
    COCOON '99.
  35. Multi-coloring trees. (with Guy Kortsarz, Andrzej Proskurowski, Hadas Shachnai, Ravit Salman, Jan Arne Telle) 
    As appearing in COCOON '99.
  36. Mod-2 Independence and Domination in Graphs. (with Jan Kratochvil, Jan Arne Telle)
    In WG '99. TR, Univ. of Bergen.
  37. Greedy local improvement and weighted set packing approximation. (with Barun Chandra)
    SODA '99.
  38. Independent sets with domination constraints. (with Jan Kratochvíl, and Jan Arne Telle)
    ICALP '98.
  39. Approximating the Generalized Block Distribution of a Matrix. (with Bengt Aspvall and Fredrik Manne)
    SWAT '98
  40. Approximation and Special Cases of Common Subtrees and Editing Distance.   (with Keisuke Tanaka)
    ISAAC '96 
  41. Facility Dispersion and Remote Subgraphs. (with Barun Chandra)
    SWAT '96
  42. Approximating k-Set Cover and Complementary Graph Coloring. 
    IPCO '96
  43. Greedy Approximations of Independent Sets in Low Degree Graphs. (with Kiyohito Yoshihara)
    ISAAC '95
  44. Approximating Discrete Collections via Local Improvements 
    SODA '95
  45. Finding Subsets Maximizing Minimum Structures. (with Kazuo Iwano, Naoki Katoh, and Takeshi Tokuyama)
    SODA '95.
  46. On the approximation of largest common point sets and largest common subtrees. (with Tatsuya Akutsu)
    ISAAC '94
  47. Improved approximations of independent sets in bounded-degree graphs. (with Jaikumar Radhakrishnan)
    SWAT '94
  48. Greed is good: approximating independent sets in sparse and bounded-degree graphs. (with Jaikumar Radhakrishnan)
    STOC '94
  49. On some communication complexity problems related to threshold functions  (with K. V. Subrahmanyam, and Jaikumar Radhakrishnan)
    FSTTCS '93
  50. Directed vs. undirected monotone contact networks for threshold functions. (with K. V. Subrahmanyam, and Jaikumar Radhakrishnan)
    FOCS '93.
  51. Parallel and on-line graph coloring. 
    In Proc. of 3rd International Symposium on Algorithms and Computation, pages 61--70, Nagoya, Japan, December 1992. Springer-Verlag LNCS #650. Received the Best Paper Award.
  52. Approximating Steiner trees in graphs with restricted weights. (with Shuichi Ueno, Hiroshi Nakao, and Yoji Kajitani)
    In Proc. of 1st Asia-Pacific Conference on Circuits and Systems, pages 69--73, Sidney, Australia, December 1992.
  53. Lower bounds for on-line graph coloring. (with Mario Szegedy)
    In Proc. of 3rd SIAM/ACM Symposium on Discrete Algorithms, Florida, pages 211--216, January 1992.
  54. Approximating maximum independent sets by excluding subgraphs (with Ravi B. Boppana)
    In Proc. of 2nd Scand. Workshop on Algorithm Theory. Lecture Notes in Computer Science #447, pages 13--25. Springer-Verlag, July 1990.

Journal Publications

The following works are the last versions leaving my hands. They may not incorporate corrections made in galley proofs or copyediting.
  1. On spectrum sharing games.
    (with Joe Halpern, Li Li, and Vahab Mirrokni). Accepted to Distributed Computing, February 2010.
  2. Approximating Independent Sets in Bounded-Degree Hypergraphs.
    (with Elena Losievskaja). Discrete Applied Mathematics 157 (2009) 1773--1786, 2009.
  3. Approximation algorithms for the weighted independent set problem in sparse graphs.
    (with Akihisa Kako, Takao Ono, and Tomio Hirata) Discrete Applied Mathematics, April 2009.
  4. Scheduling with conflicts: Online and offline algorithms.
    (with Guy Even, Lotem Kaplan, and Dana Ron) Journal of Scheduling, April 2009.
  5. Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
    Algorithmica, Dec 2009 (with Leah Epstein, Asaf Levin, Hadas Shachnai)
  6. Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
    (With Takeshi Tokuyama) Theoretical Computer Science, 2008.
  7. Improved Bounds for Sum Multicoloring and Weighted Completion Time of Dependent Jobs.
    ACM Transactions on Algorithms, March 2008. (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai)
  8. Complete Partitions of Graphs.
    Combinatorica 2007. (with Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian)
  9. Vertex coloring acyclic digraphs and their corresponding hypergraphs.
    (With Geir Agnarsson and {\'A}g{\'u}st Egilsson.) Discrete Applied Mathematics, 2007.
  10. Improved approximation of the stable marriage problem.
    ACM Transactions on Algorithms (with Shuichi Miyazaki, K. Iwama, K. Yanagisawa), 2007
  11. Strongly Simplicial Vertices of Powers of Trees
    (with Geir Agnarsson) Discrete Mathematics, 2007.
  12. Scheduling Split Interval Graphs. (with Reuven Bar-Yehuda, Seffi Naor, Hadas Shachnai, and Irina Shapira)
    SIAM Journal of Computing, Vol. 36, No. 1, 1--15, 2006.
  13. Approximating the $(h,k)$-labelling problem. Int. J. Mobile Mobile Network Design and Innovation, Vol. 1, No. 2, 113--117, 2006.
  14. Improved results for data migration and open-shop scheduling. ACM Transactions on Algorithms 2006. (with Rajiv Gandhi, Magnús M. Halldórsson, G. Kortsarz and H. Shachnai)
  15. Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. Information Processing Letters, 2005. 94(2):49–53, 30 April 2005. (with Artur Czumaj, Andrzej Lingas, and Johan Nilsson)
  16. Randomized approximation of the stable marriage problem. Theoretical Computer Science 325(3):439–465, 2004. (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa)
  17. Powers of Geometric Intersection Graphs and Dispersion Algorithms (with Geir Agnarsson, Peter Damaschke)
    Discrete Applied Mathematics, 2003
  18. Coloring Squares of Graphs. (with Geir Agnarsson)
    SIAM J. Discrete Math. 2003
  19. Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs. (with Guy Kortsarz and Hadas Shachnai)
    Algorithmica, 2003
  20. Approximation algorithms for the minimum test set problem (with Koen M.J. De Bontridder, Bjarni V. Halldórsson, Cor A.J. Hurkens, Jan K. Lenstra, R. Ravi, and Leen Stougie)
    Mathematical Programming-B, 2003
  21. Approximability results for the stable marriage problem with ties. (with Robert W. Irving, Kazuo Iwama, David F. Manlove, Shuichi Miyazaki, Yasufumi Morita, and Sandy Scott)
    Theoretical Computer Science 2003
  22. Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees. (with Guy Kortsarz)
    Journal of Algorithms, 42(2), 334-366, February 2002.
  23. Online Independent Sets (with Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi)
    Theoretical Computer Science, 289(2), 953--962, October 2002.
  24. Approximating the domatic number (with Uriel Feige, Guy Kortsarz, and Arvind Srinivasan)
    SIAM Journal of Computing 32(1), 172--195, December 2002.
  25. Multicoloring Trees.  (with Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, and Jan Arne Telle)
    Information and Computation, Available online 12 December 2002.
  26. Approximations for the Generalized Block Distribution of a Matrix. (with Bengt Aspvall and  and Fredrik Manne)
    Theoretical Computer Science 262(1-2), 145--160, July 2001.
  27. Online coloring known graphs.  
    In Electronic J. of Combinatorics. (Feb 2000)
  28. Mod-2 Independence and Domination in Graphs.  (with Jan Kratochvil, Jan Arne Telle)
    Discrete Applied Math. Earlier version appears in WG '99, LNCS.
  29. Sum Multicoloring of Graphs. (with Amotz Bar-Noy, Guy Kortsarz, Hadas Shachnai, Ravit Salman)
    Journal of Algorithms (Mar 2000). Extended abstract appears in ESA '99.
  30. Approximations of Weighted Independent Set and Hereditary Subset Problems. 
    Journal of Graphs Algorithms and Applications    , Vol.4, No.1, pp.1-16.
  31. Approximation Algorithms for Dispersion Problems.  (with Barun Chandra)
    Journal of Algorithms, April 2000.
  32. Powers of chordal graphs and their coloring.  (with Geir Agnarsson, Ray Greenlaw)
    Congressus Numerantium    , (since Sept 2000).
  33. Greedy local improvement and weighted set packing approximation (with Barun Chandra)
    Journal of Algorithms, 39(2), 223-240, May 2000. (Abstract ) 
  34. A matched approximation bound for the sum of a greedy coloring. (with Amotz Bar-Noy and Guy Kortsarz)
    Information Processing Letters     71, 135-140, 1999.
  35. Finding Subsets Maximizing Minimum Structures. (with Kazuo Iwano, Naoki Katoh, and Takeshi Tokuyama)
    SIAM Journal of Discrete Math     12(3), 342-359, 1999.
  36. On the approximation of largest common point sets and largest common subtrees.  (with Tatsuya Akutsu)
    Theoretical Computer Science    . 233(1-2), 33-50, 17 Dec 1999.
  37. Independent sets with domination constraints. (with Jan Kratochvíl, Jan Arne Telle)
    Discrete Applied Mathematics, 99(1-3), 39-54, 17 Dec 1999.
  38. On Chromatic Sums and Distributed Resource Allocation.  (with Amotz Bar-Noy, Mihir Bellare,  Hadas Shachnai, and Tami Tamir)
    Information and Computation     140(2), February 1998.
  39. Approximating Steiner trees in graphs with restricted weights.  (with Shuichi Ueno, Hiroshi Nakao, and Yoji Kajitani)
    Networks     31(4), 283-292, 1998.
  40. Greed is good: Approximating independent sets in sparse and bounded-degree graphs.  (with Jaikumar Radhakrishnan)
    Algorithmica     18:143-163 (1997). Special issue on on approximation algorithms.
  41. Parallel and online graph coloring.  
    Journal of Algorithms,     23: 265-280 (1997).
  42. Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring. (with Hoong-Chuin Lau)
    Journal of Graph Algorithms and Applications, 1(3):1--13, Nov. 1997
  43. Lower bounds for on-line graph coloring. (with Mario Szegedy)
    Theoretical Computer Science    , 130:163--174, August 1994.
  44. Improved approximations of bounded-degree independent sets via subgraph removal. (with Jaikumar Radhakrishnan)
    In a special issue of Nordic J. Computing, 1(4):475--492, Winter 1994.
    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.
  45. A still better performance guarantee for approximate graph coloring. 
    Information Processing Letters    , 45:19--23, 25 January 1993.
  46. Approximating the minimum maximal independence number.  Information Processing Letters, 46:169--172, 25 June 1993.
  47. Approximating the tree and tour covers of a graph.  (with Estie Arkin and Rafi  Hassin)
    Information Processing Letters, 47:275--282, 18 October 1993.
  48. Approximating maximum independent sets by excluding subgraphs. (with Ravi B. Boppana)
    BIT    , 32(2):180--196, June 1992.

Book chapters

  1. Multicoloring: Problems and Techniques. Invited paper to MFCS '04.
  2. Approximations of independent sets in graphs.  Invited survey paper, from APPROX '98.

Unrefereed Manuscripts

Papers in Icelandic

Thesis

Student Publications

Last revised February 2010, Magnus M Halldorsson