 | 2009 |
|---|
| 102 |       | Magnús M. Halldórsson:
Wireless Scheduling with Power Control.
ESA 2009: 361-372 |
| 101 | | Geir Agnarsson,
Magnús M. Halldórsson,
Elena Losievskaja:
SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs.
ICALP (1) 2009: 12-23 |
| 100 | | Magnús M. Halldórsson,
Roger Wattenhofer:
Wireless Communication Is in APX.
ICALP (1) 2009: 525-536 |
| 99 | | Leah Epstein,
Magnús M. Halldórsson,
Asaf Levin,
Hadas Shachnai:
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
Algorithmica 55(4): 643-665 (2009) |
| 98 | | Akihisa Kako,
Takao Ono,
Tomio Hirata,
Magnús M. Halldórsson:
Approximation algorithms for the weighted independent set problem in sparse graphs.
Discrete Applied Mathematics 157(4): 617-626 (2009) |
| 97 | | Magnús M. Halldórsson,
Elena Losievskaja:
Independent sets in bounded-degree hypergraphs.
Discrete Applied Mathematics 157(8): 1773-1786 (2009) |
| 96 | | Guy Even,
Magnús M. Halldórsson,
Lotem Kaplan,
Dana Ron:
Scheduling with conflicts: online and offline algorithms.
J. Scheduling 12(2): 199-224 (2009) |
| 2008 |
|---|
| 95 |  | Luca Aceto,
Ivan Damgård,
Leslie Ann Goldberg,
Magnús M. Halldórsson,
Anna Ingólfsdóttir,
Igor Walukiewicz:
Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games
Springer 2008 |
| 94 | | Luca Aceto,
Ivan Damgård,
Leslie Ann Goldberg,
Magnús M. Halldórsson,
Anna Ingólfsdóttir,
Igor Walukiewicz:
Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations
Springer 2008 |
| 93 | | Magnús M. Halldórsson,
Guy Kortsarz,
Maxim Sviridenko:
Min Sum Edge Coloring in Multigraphs Via Configuration LP.
IPCO 2008: 359-373 |
| 92 | | Takuro Fukunaga,
Magnús M. Halldórsson,
Hiroshi Nagamochi:
Robust cost colorings.
SODA 2008: 1204-1212 |
| 91 | | Magnús M. Halldórsson,
Hadas Shachnai:
Batch Coloring Flat Graphs and Thin.
SWAT 2008: 198-209 |
| 90 | | Rajiv Gandhi,
Magnús M. Halldórsson,
Guy Kortsarz,
Hadas Shachnai:
Improved bounds for scheduling conflicting jobs with minsum criteria.
ACM Transactions on Algorithms 4(1): (2008) |
| 89 | | Geir Agnarsson,
Ágúst S. Egilsson,
Magnús M. Halldórsson:
Vertex coloring acyclic digraphs and their corresponding hypergraphs.
Discrete Applied Mathematics 156(10): 1918-1928 (2008) |
| 88 | | Magnús M. Halldórsson,
Takeshi Tokuyama:
Minimizing interference of a wireless ad-hoc network in a plane.
Theor. Comput. Sci. 402(1): 29-42 (2008) |
| 2007 |
|---|
| 87 | | Takuro Fukunaga,
Magnús M. Halldórsson,
Hiroshi Nagamochi:
"Rent-or-Buy" Scheduling and Cost Coloring Problems.
FSTTCS 2007: 84-95 |
| 86 | | Magnús M. Halldórsson,
Elena Losievskaja:
Independent Sets in Bounded-Degree Hypergraphs.
WADS 2007: 263-274 |
| 85 | | Magnús M. Halldórsson,
Christian Knauer,
Andreas Spillner,
Takeshi Tokuyama:
Fixed-Parameter Tractability for Non-Crossing Spanning Trees.
WADS 2007: 410-421 |
| 84 | | Magnús M. Halldórsson,
Kazuo Iwama,
Shuichi Miyazaki,
Hiroki Yanagisawa:
Improved approximation results for the stable marriage problem.
ACM Transactions on Algorithms 3(3): (2007) |
| 83 | | Geir Agnarsson,
Magnús M. Halldórsson:
Strongly simplicial vertices of powers of trees.
Discrete Mathematics 307(21): 2647-2652 (2007) |
| 2006 |
|---|
| 82 | | Magnús M. Halldórsson,
Takeshi Tokuyama:
Minimizing Interference of a Wireless Ad-Hoc Network in a Plane.
ALGOSENSORS 2006: 71-82 |
| 81 | | Leah Epstein,
Magnús M. Halldórsson,
Asaf Levin,
Hadas Shachnai:
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
APPROX-RANDOM 2006: 116-127 |
| 80 | | Magnús M. Halldórsson,
Ragnar K. Karlsson:
Strip Graphs: Recognition and Scheduling.
WG 2006: 137-146 |
| 79 | | Rajiv Gandhi,
Magnús M. Halldórsson,
Guy Kortsarz,
Hadas Shachnai:
Improved results for data migration and open shop scheduling.
ACM Transactions on Algorithms 2(1): 116-129 (2006) |
| 78 | | Reuven Bar-Yehuda,
Magnús M. Halldórsson,
Joseph Naor,
Hadas Shachnai,
Irina Shapira:
Scheduling Split Intervals.
SIAM J. Comput. 36(1): 1-15 (2006) |
| 2005 |
|---|
| 77 | | Akihisa Kako,
Takao Ono,
Tomio Hirata,
Magnús M. Halldórsson:
Approximation Algorithms for the Weighted Independent Set Problem.
WG 2005: 341-350 |
| 76 | | Artur Czumaj,
Magnús M. Halldórsson,
Andrzej Lingas,
Johan Nilsson:
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth.
Inf. Process. Lett. 94(2): 49-53 (2005) |
| 2004 |
|---|
| 75 | | Rajiv Gandhi,
Magnús M. Halldórsson,
Guy Kortsarz,
Hadas Shachnai:
Improved Results for Data Migration and Open Shop Scheduling.
ICALP 2004: 658-669 |
| 74 | | Magnús M. Halldórsson,
Guy Kortsarz:
Multicoloring: Problems and Techniques.
MFCS 2004: 25-41 |
| 73 | | Magnús M. Halldórsson,
Joseph Y. Halpern,
Erran L. Li,
Vahab S. Mirrokni:
On spectrum sharing games.
PODC 2004: 107-114 |
| 72 | | Geir Agnarsson,
Magnús M. Halldórsson:
On colorings of squares of outerplanar graphs.
SODA 2004: 244-253 |
| 71 | | Geir Agnarsson,
Magnús M. Halldórsson:
Strong Colorings of Hypergraphs.
WAOA 2004: 253-266 |
| 70 | | Rajiv Gandhi,
Magnús M. Halldórsson,
Guy Kortsarz,
Hadas Shachnai:
Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria.
WAOA 2004: 68-82 |
| 69 | | Magnús M. Halldórsson,
Kazuo Iwama,
Shuichi Miyazaki,
Hiroki Yanagisawa:
Randomized approximation of the stable marriage problem.
Theor. Comput. Sci. 325(3): 439-465 (2004) |
| 2003 |
|---|
| 68 | | Geir Agnarsson,
Ágúst S. Egilsson,
Magnús M. Halldórsson:
Proper Down-Coloring Simple Acyclic Digraphs.
AGTIVE 2003: 299-312 |
| 67 | | Magnús M. Halldórsson,
Kazuo Iwama,
Shuichi Miyazaki,
Hiroki Yanagisawa:
Randomized Approximation of the Stable Marriage Problem.
COCOON 2003: 339-350 |
| 66 | | Magnús M. Halldórsson,
Kazuo Iwama,
Shuichi Miyazaki,
Hiroki Yanagisawa:
Improved Approximation of the Stable Marriage Problem.
ESA 2003: 266-277 |
| 65 | | Magnús M. Halldórsson,
Guy Kortsarz,
Hadas Shachnai:
Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.
Algorithmica 37(3): 187-209 (2003) |
| 64 | | Geir Agnarsson,
Peter Damaschke,
Magnús M. Halldórsson:
Powers of geometric intersection graphs and dispersion algorithms.
Discrete Applied Mathematics 132(1-3): 3-16 (2003) |
| 63 | | Magnús M. Halldórsson,
Guy Kortsarz,
Andrzej Proskurowski,
Ravit Salman,
Hadas Shachnai,
Jan Arne Telle:
Multicoloring trees.
Inf. Comput. 180(2): 113-129 (2003) |
| 62 | | Geir Agnarsson,
Magnús M. Halldórsson:
Coloring Powers of Planar Graphs.
SIAM J. Discrete Math. 16(4): 651-662 (2003) |
| 61 | | Magnús M. Halldórsson,
Robert W. Irving,
Kazuo Iwama,
David Manlove,
Shuichi Miyazaki,
Yasufumi Morita,
Sandy Scott:
Approximability results for stable marriage problems with ties.
Theor. Comput. Sci. 306(1-3): 431-447 (2003) |
| 2002 |
|---|
| 60 | | Magnús M. Halldórsson,
Kazuo Iwama,
Shuichi Miyazaki,
Yasufumi Morita:
Inapproximability Results on Stable Marriage Problems.
LATIN 2002: 554-568 |
| 59 | | Reuven Bar-Yehuda,
Magnús M. Halldórsson,
Joseph Naor,
Hadas Shachnai,
Irina Shapira:
Scheduling split intervals.
SODA 2002: 732-741 |
| 58 | | Geir Agnarsson,
Peter Damaschke,
Magnús M. Halldórsson:
Powers of Geometric Intersection Graphs and Dispersion Algorithms.
SWAT 2002: 140-149 |
| 57 | | Magnús M. Halldórsson,
Guy Kortsarz:
Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees.
J. Algorithms 42(2): 334-366 (2002) |
| 56 | | Uriel Feige,
Magnús M. Halldórsson,
Guy Kortsarz,
Aravind Srinivasan:
Approximating the Domatic Number.
SIAM J. Comput. 32(1): 172-195 (2002) |
| 55 | | Magnús M. Halldórsson,
Kazuo Iwama,
Shuichi Miyazaki,
Shiro Taketomi:
Online independent sets.
Theor. Comput. Sci. 289(2): 953-962 (2002) |
| 2001 |
|---|
| 54 | | Bjarni V. Halldórsson,
Magnús M. Halldórsson,
R. Ravi:
On the Approximability of the Minimum Test Collection Problem.
ESA 2001: 158-169 |
| 53 | | Magnús M. Halldórsson,
Guy Kortsarz,
Hadas Shachnai:
Minimizing Average Completion of Dedicated Tasks and Interval Graphs.
RANDOM-APPROX 2001: 114-126 |
| 52 | | Barun Chandra,
Magnús M. Halldórsson:
Approximation Algorithms for Dispersion Problems.
J. Algorithms 38(2): 438-465 (2001) |
| 51 | | Barun Chandra,
Magnús M. Halldórsson:
Greedy Local Improvement and Weighted Set Packing Approximation.
J. Algorithms 39(2): 223-240 (2001) |
| 50 | | Bengt Aspvall,
Magnús M. Halldórsson,
Fredrik Manne:
Approximations for the general block distribution of a matrix.
Theor. Comput. Sci. 262(1): 145-160 (2001) |
| 2000 |
|---|
| 49 | | Magnús M. Halldórsson:
Algorithm Theory - SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings
Springer 2000 |
| 48 | | Magnús M. Halldórsson,
Kazuo Iwama,
Shuichi Miyazaki,
Shiro Taketomi:
Online Independent Sets.
COCOON 2000: 202-209 |
| 47 | | Takao Asano,
Magnús M. Halldórsson,
Kazuo Iwama,
Takeshi Matsuda:
Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.
ISAAC 2000: 204-215 |
| 46 | | Geir Agnarsson,
Magnús M. Halldórsson:
Coloring powers of planar graphs.
SODA 2000: 654-662 |
| 45 | | Uriel Feige,
Magnús M. Halldórsson,
Guy Kortsarz:
Approximating the domatic number.
STOC 2000: 134-143 |
| 44 | | Magnús M. Halldórsson,
Jan Kratochvíl,
Jan Arne Telle:
Independent Sets with Domination Constraints.
Discrete Applied Mathematics 99(1-3): 39-54 (2000) |
| 43 | | Magnús M. Halldórsson:
Online Coloring Known Graphs.
Electr. J. Comb. 7: (2000) |
| 42 | | Magnús M. Halldórsson,
Jan Kratochvíl,
Jan Arne Telle:
Mod-2 Independence and Domination in Graphs.
Int. J. Found. Comput. Sci. 11(3): 355-363 (2000) |
| 41 | | Amotz Bar-Noy,
Magnús M. Halldórsson,
Guy Kortsarz,
Ravit Salman,
Hadas Shachnai:
Sum Multicoloring of Graphs.
J. Algorithms 37(2): 422-450 (2000) |
| 40 | | Magnús M. Halldórsson:
Approximations of Weighted Independent Set and Hereditary Subset Problems.
J. Graph Algorithms Appl. 4(1): (2000) |
| 39 | | Magnús M. Halldórsson:
Guest Editor's Foreword.
Nord. J. Comput. 7(3): 149-150 (2000) |
| 38 | | Tatsuya Akutsu,
Magnús M. Halldórsson:
On the approximation of largest common subtrees and largest common point sets.
Theor. Comput. Sci. 233(1-2): 33-50 (2000) |
| 1999 |
|---|
| 37 | | Magnús M. Halldórsson:
Approximations of Weighted Independent Set and Hereditary Subset Problems.
COCOON 1999: 261-270 |
| 36 | | Magnús M. Halldórsson,
Guy Kortsarz,
Andrzej Proskurowski,
Ravit Salman,
Hadas Shachnai,
Jan Arne Telle:
Multi-coloring Trees.
COCOON 1999: 271-280 |
| 35 | | Amotz Bar-Noy,
Magnús M. Halldórsson,
Guy Kortsarz,
Ravit Salman,
Hadas Shachnai:
Sum Multi-coloring of Graphs.
ESA 1999: 390-401 |
| 34 | | Magnús M. Halldórsson,
Guy Kortsarz:
Multicoloring Planar Graphs and Partial k-Trees.
RANDOM-APPROX 1999: 73-84 |
| 33 | | Barun Chandra,
Magnús M. Halldórsson:
Greedy Local Improvement and Weighted Set Packing Approximation.
SODA 1999: 169-176 |
| 32 | | Magnús M. Halldórsson:
Online Coloring Known Graphs.
SODA 1999: 917-918 |
| 31 | | Magnús M. Halldórsson,
Jan Kratochvíl,
Jan Arne Telle:
Mod-2 Independence and Domination in Graphs.
WG 1999: 101-109 |
| 30 | | Amotz Bar-Noy,
Magnús M. Halldórsson,
Guy Kortsarz:
A Matched Approximation Bound for the Sum of a Greedy Coloring.
Inf. Process. Lett. 71(3-4): 135-140 (1999) |
| 29 | | Magnús M. Halldórsson,
Kazuo Iwano,
Naoki Katoh,
Takeshi Tokuyama:
Finding Subsets Maximizing Minimum Structures.
SIAM J. Discrete Math. 12(3): 342-359 (1999) |
| 1998 |
|---|
| 28 | | Magnús M. Halldórsson:
Approximations of Independent Sets in Graphs.
APPROX 1998: 1-13 |
| 27 | | Magnús M. Halldórsson,
Jan Kratochvíl,
Jan Arne Telle:
Independent Sets with Domination Constraints.
ICALP 1998: 176-187 |
| 26 | | Bengt Aspvall,
Magnús M. Halldórsson,
Fredrik Manne:
Approximations for the General Block Distribution of a Matrix.
SWAT 1998: 47-58 |
| 25 | | Amotz Bar-Noy,
Mihir Bellare,
Magnús M. Halldórsson,
Hadas Shachnai,
Tami Tamir:
On Chromatic Sums and Distributed Resource Allocation.
Inf. Comput. 140(2): 183-202 (1998) |
| 24 | | Magnús M. Halldórsson,
Shuichi Ueno,
Hiroshi Nakao,
Yoji Kajitani:
Approximating Steiner trees in graphs with restricted weights.
Networks 31(4): 283-292 (1998) |
| 1997 |
|---|
| 23 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan:
Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs.
Algorithmica 18(1): 145-163 (1997) |
| 22 | | Magnús M. Halldórsson:
Parallel and On-Line Graph Coloring.
J. Algorithms 23(2): 265-280 (1997) |
| 21 | | Magnús M. Halldórsson,
Hoong Chuin Lau:
Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring.
J. Graph Algorithms Appl. 1: (1997) |
| 1996 |
|---|
| 20 | | Magnús M. Halldórsson:
Approximating k-Set Cover and Complementary Graph Coloring.
IPCO 1996: 118-131 |
| 19 | | Magnús M. Halldórsson,
Keisuke Tanaka:
Approximation and Special Cases of Common Subtrees and Editing Distance.
ISAAC 1996: 75-84 |
| 18 | | Barun Chandra,
Magnús M. Halldórsson:
Facility Dispersion and Remote Subgraphs.
SWAT 1996: 53-65 |
| 1995 |
|---|
| 17 | | Magnús M. Halldórsson,
Kiyohito Yoshihara:
Greedy Approximations of Independent Sets in Low Degree Graphs.
ISAAC 1995: 152-161 |
| 16 | | Magnús M. Halldórsson,
Kazuo Iwano,
Naoki Katoh,
Takeshi Tokuyama:
Finding Subsets Maximizing Minimum Structures.
SODA 1995: 150-159 |
| 15 | | Magnús M. Halldórsson:
Approximating Discrete Collections via Local Improvements.
SODA 1995: 160-169 |
| 1994 |
|---|
| 14 | | Tatsuya Akutsu,
Magnús M. Halldórsson:
On the Approximation of Largest Common Subtrees and Largest Common Point Sets.
ISAAC 1994: 405-413 |
| 13 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan:
Greed is good: approximating independent sets in sparse and bounded-degree graphs.
STOC 1994: 439-448 |
| 12 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan:
Improved Approximations of Independent Sets in Bounded-Degree Graphs.
SWAT 1994: 195-206 |
| 11 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan:
Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal.
Nord. J. Comput. 1(4): 475-492 (1994) |
| 10 | | Magnús M. Halldórsson,
Mario Szegedy:
Lower Bounds for On-Line Graph Coloring.
Theor. Comput. Sci. 130(1): 163-174 (1994) |
| 1993 |
|---|
| 9 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan,
K. V. Subrahmanyam:
Directed vs. Undirected Monotone Contact Networks for Threshold Functions
FOCS 1993: 604-613 |
| 8 | | Magnús M. Halldórsson,
Jaikumar Radhakrishnan,
K. V. Subrahmanyam:
On Some Communication Complexity Problems Related to THreshold Functions.
FSTTCS 1993: 248-259 |
| 7 | | Magnús M. Halldórsson:
A Still Better Performance Guarantee for Approximate Graph Coloring.
Inf. Process. Lett. 45(1): 19-23 (1993) |
| 6 | | Magnús M. Halldórsson:
Approximating the Minimum Maximal Independence Number.
Inf. Process. Lett. 46(4): 169-172 (1993) |
| 5 | | Esther M. Arkin,
Magnús M. Halldórsson,
Refael Hassin:
Approximating the Tree and Tour Covers of a Graph.
Inf. Process. Lett. 47(6): 275-282 (1993) |
| 1992 |
|---|
| 4 | | Magnús M. Halldórsson:
Parallel and On-line Graph Coloring Algorithms.
ISAAC 1992: 61-70 |
| 3 | | Magnús M. Halldórsson,
Mario Szegedy:
Lower Bounds for On-Line Graph Coloring.
SODA 1992: 211-216 |
| 2 | | Ravi B. Boppana,
Magnús M. Halldórsson:
Approximating Maximum Independent Sets by Excluding Subgraphs.
BIT 32(2): 180-196 (1992) |
| 1990 |
|---|
| 1 | | Ravi B. Boppana,
Magnús M. Halldórsson:
Approximating Maximum Independent Sets by Excluding Subgraphs.
SWAT 1990: 13-25 |
