dblp.uni-trier.dewww.uni-trier.de

Magnús M. Halldórsson Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
102EEMagnús M. Halldórsson: Wireless Scheduling with Power Control. ESA 2009: 361-372
101EEGeir Agnarsson, Magnús M. Halldórsson, Elena Losievskaja: SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs. ICALP (1) 2009: 12-23
100EEMagnús M. Halldórsson, Roger Wattenhofer: Wireless Communication Is in APX. ICALP (1) 2009: 525-536
99EELeah 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)
98EEAkihisa 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)
97EEMagnús M. Halldórsson, Elena Losievskaja: Independent sets in bounded-degree hypergraphs. Discrete Applied Mathematics 157(8): 1773-1786 (2009)
96EEGuy 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
93EEMagnús M. Halldórsson, Guy Kortsarz, Maxim Sviridenko: Min Sum Edge Coloring in Multigraphs Via Configuration LP. IPCO 2008: 359-373
92EETakuro Fukunaga, Magnús M. Halldórsson, Hiroshi Nagamochi: Robust cost colorings. SODA 2008: 1204-1212
91EEMagnús M. Halldórsson, Hadas Shachnai: Batch Coloring Flat Graphs and Thin. SWAT 2008: 198-209
90EERajiv 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)
89EEGeir 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)
88EEMagnú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
87EETakuro Fukunaga, Magnús M. Halldórsson, Hiroshi Nagamochi: "Rent-or-Buy" Scheduling and Cost Coloring Problems. FSTTCS 2007: 84-95
86EEMagnús M. Halldórsson, Elena Losievskaja: Independent Sets in Bounded-Degree Hypergraphs. WADS 2007: 263-274
85EEMagnús M. Halldórsson, Christian Knauer, Andreas Spillner, Takeshi Tokuyama: Fixed-Parameter Tractability for Non-Crossing Spanning Trees. WADS 2007: 410-421
84EEMagnú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)
83EEGeir Agnarsson, Magnús M. Halldórsson: Strongly simplicial vertices of powers of trees. Discrete Mathematics 307(21): 2647-2652 (2007)
2006
82EEMagnús M. Halldórsson, Takeshi Tokuyama: Minimizing Interference of a Wireless Ad-Hoc Network in a Plane. ALGOSENSORS 2006: 71-82
81EELeah Epstein, Magnús M. Halldórsson, Asaf Levin, Hadas Shachnai: Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs. APPROX-RANDOM 2006: 116-127
80EEMagnús M. Halldórsson, Ragnar K. Karlsson: Strip Graphs: Recognition and Scheduling. WG 2006: 137-146
79EERajiv 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)
78EEReuven 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
77EEAkihisa Kako, Takao Ono, Tomio Hirata, Magnús M. Halldórsson: Approximation Algorithms for the Weighted Independent Set Problem. WG 2005: 341-350
76EEArtur 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
75EERajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Improved Results for Data Migration and Open Shop Scheduling. ICALP 2004: 658-669
74EEMagnús M. Halldórsson, Guy Kortsarz: Multicoloring: Problems and Techniques. MFCS 2004: 25-41
73EEMagnús M. Halldórsson, Joseph Y. Halpern, Erran L. Li, Vahab S. Mirrokni: On spectrum sharing games. PODC 2004: 107-114
72EEGeir Agnarsson, Magnús M. Halldórsson: On colorings of squares of outerplanar graphs. SODA 2004: 244-253
71EEGeir Agnarsson, Magnús M. Halldórsson: Strong Colorings of Hypergraphs. WAOA 2004: 253-266
70EERajiv 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
69EEMagnú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
68EEGeir Agnarsson, Ágúst S. Egilsson, Magnús M. Halldórsson: Proper Down-Coloring Simple Acyclic Digraphs. AGTIVE 2003: 299-312
67EEMagnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa: Randomized Approximation of the Stable Marriage Problem. COCOON 2003: 339-350
66EEMagnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa: Improved Approximation of the Stable Marriage Problem. ESA 2003: 266-277
65EEMagnú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)
64EEGeir 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)
63EEMagnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, Jan Arne Telle: Multicoloring trees. Inf. Comput. 180(2): 113-129 (2003)
62EEGeir Agnarsson, Magnús M. Halldórsson: Coloring Powers of Planar Graphs. SIAM J. Discrete Math. 16(4): 651-662 (2003)
61EEMagnú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
60EEMagnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita: Inapproximability Results on Stable Marriage Problems. LATIN 2002: 554-568
59EEReuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira: Scheduling split intervals. SODA 2002: 732-741
58EEGeir Agnarsson, Peter Damaschke, Magnús M. Halldórsson: Powers of Geometric Intersection Graphs and Dispersion Algorithms. SWAT 2002: 140-149
57EEMagnú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)
56EEUriel 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
54EEBjarni V. Halldórsson, Magnús M. Halldórsson, R. Ravi: On the Approximability of the Minimum Test Collection Problem. ESA 2001: 158-169
53EEMagnú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)
50EEBengt 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
48EEMagnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Shiro Taketomi: Online Independent Sets. COCOON 2000: 202-209
47EETakao 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
46EEGeir Agnarsson, Magnús M. Halldórsson: Coloring powers of planar graphs. SODA 2000: 654-662
45EEUriel Feige, Magnús M. Halldórsson, Guy Kortsarz: Approximating the domatic number. STOC 2000: 134-143
44EEMagnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle: Independent Sets with Domination Constraints. Discrete Applied Mathematics 99(1-3): 39-54 (2000)
43EEMagnú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)
40EEMagnú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)
38EETatsuya 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
37EEMagnús M. Halldórsson: Approximations of Weighted Independent Set and Hereditary Subset Problems. COCOON 1999: 261-270
36EEMagnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, Jan Arne Telle: Multi-coloring Trees. COCOON 1999: 271-280
35EEAmotz 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
33EEBarun Chandra, Magnús M. Halldórsson: Greedy Local Improvement and Weighted Set Packing Approximation. SODA 1999: 169-176
32EEMagnús M. Halldórsson: Online Coloring Known Graphs. SODA 1999: 917-918
31EEMagnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle: Mod-2 Independence and Domination in Graphs. WG 1999: 101-109
30EEAmotz 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)
29EEMagnú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
28EEMagnús M. Halldórsson: Approximations of Independent Sets in Graphs. APPROX 1998: 1-13
27EEMagnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle: Independent Sets with Domination Constraints. ICALP 1998: 176-187
26EEBengt 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)
24EEMagnú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)
21EEMagnú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
20EEMagnús M. Halldórsson: Approximating k-Set Cover and Complementary Graph Coloring. IPCO 1996: 118-131
19EEMagnús M. Halldórsson, Keisuke Tanaka: Approximation and Special Cases of Common Subtrees and Editing Distance. ISAAC 1996: 75-84
18EEBarun Chandra, Magnús M. Halldórsson: Facility Dispersion and Remote Subgraphs. SWAT 1996: 53-65
1995
17EEMagnú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
14EETatsuya Akutsu, Magnús M. Halldórsson: On the Approximation of Largest Common Subtrees and Largest Common Point Sets. ISAAC 1994: 405-413
13EEMagnús M. Halldórsson, Jaikumar Radhakrishnan: Greed is good: approximating independent sets in sparse and bounded-degree graphs. STOC 1994: 439-448
12EEMagnú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
8EEMagnú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
4EEMagnús M. Halldórsson: Parallel and On-line Graph Coloring Algorithms. ISAAC 1992: 61-70
3EEMagnú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
1EERavi B. Boppana, Magnús M. Halldórsson: Approximating Maximum Independent Sets by Excluding Subgraphs. SWAT 1990: 13-25

Coauthor Index

1Luca Aceto [94] [95]
2Geir Agnarsson [46] [58] [62] [64] [68] [71] [72] [83] [89] [101]
3Tatsuya Akutsu [14] [38]
4Esther M. Arkin [5]
5Takao Asano [47]
6Bengt Aspvall [26] [50]
7Amotz Bar-Noy [25] [30] [35] [41]
8Reuven Bar-Yehuda [59] [78]
9Mihir Bellare [25]
10Ravi B. Boppana [1] [2]
11Barun Chandra [18] [33] [51] [52]
12Artur Czumaj [76]
13Peter Damaschke [58] [64]
14Ivan Damgård [94] [95]
15Ágúst S. Egilsson [68] [89]
16Leah Epstein [81] [99]
17Guy Even [96]
18Uriel Feige [45] [56]
19Takuro Fukunaga [87] [92]
20Rajiv Gandhi [70] [75] [79] [90]
21Leslie Ann Goldberg [94] [95]
22Bjarni V. Halldórsson [54]
23Joseph Y. Halpern [73]
24Refael Hassin [5]
25Tomio Hirata [77] [98]
26Anna Ingólfsdóttir [94] [95]
27Robert W. Irving [61]
28Kazuo Iwama [47] [48] [55] [60] [61] [66] [67] [69] [84]
29Kazuo Iwano [16] [29]
30Yoji Kajitani [24]
31Akihisa Kako [77] [98]
32Lotem Kaplan [96]
33Ragnar K. Karlsson [80]
34Naoki Katoh [16] [29]
35Christian Knauer [85]
36Guy Kortsarz [30] [34] [35] [36] [41] [45] [53] [56] [57] [63] [65] [70] [74] [75] [79] [90] [93]
37Jan Kratochvíl [27] [31] [42] [44]
38Hoong Chuin Lau [21]
39Asaf Levin [81] [99]
40Erran L. Li (Li Li, Li (Erran) Li) [73]
41Andrzej Lingas [76]
42Elena Losievskaja [86] [97] [101]
43David Manlove [61]
44Fredrik Manne [26] [50]
45Takeshi Matsuda [47]
46Vahab S. Mirrokni (Seyed Vahab Mirrokni) [73]
47Shuichi Miyazaki [48] [55] [60] [61] [66] [67] [69] [84]
48Yasufumi Morita [60] [61]
49Hiroshi Nagamochi [87] [92]
50Hiroshi Nakao [24]
51Joseph Naor (Seffi Naor) [59] [78]
52Johan Nilsson [76]
53Takao Ono [77] [98]
54Andrzej Proskurowski [36] [63]
55Jaikumar Radhakrishnan [8] [9] [11] [12] [13] [23]
56R. Ravi [54]
57Dana Ron [96]
58Ravit Salman [35] [36] [41] [63]
59Sandy Scott [61]
60Hadas Shachnai [25] [35] [36] [41] [53] [59] [63] [65] [70] [75] [78] [79] [81] [90] [91] [99]
61Irina Shapira [59] [78]
62Andreas Spillner [85]
63Aravind Srinivasan [56]
64K. V. Subrahmanyam [8] [9]
65Maxim Sviridenko [93]
66Mario Szegedy [3] [10]
67Shiro Taketomi [48] [55]
68Tami Tamir [25]
69Keisuke Tanaka [19]
70Jan Arne Telle [27] [31] [36] [42] [44] [63]
71Takeshi Tokuyama [16] [29] [82] [85] [88]
72Shuichi Ueno [24]
73Igor Walukiewicz [94] [95]
74Roger Wattenhofer [100]
75Hiroki Yanagisawa [66] [67] [69] [84]
76Kiyohito Yoshihara [17]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)