×

zbMATH — the first resource for mathematics

Halldórsson, Magnús Mar

Compute Distance To:
Author ID: halldorsson.magnus-m Recent zbMATH articles by "Halldórsson, Magnús Mar"
Published as: Halldorsson, Magnus M.; Halldórsson, M. M.; Halldórsson, Magnus; Halldórsson, Magnus M.; Halldórsson, Magnús; Halldórsson, Magnús M.
Homepage: https://www.ru.is/~mmh/
External Links: MGP · Wikidata · ORCID · dblp
Documents Indexed: 176 Publications since 1992, including 9 Books
all top 5

Co-Authors

18 single-authored
19 Kortsarz, Guy
17 Shachnai, Hadas
13 Agnarsson, Geir
12 Iwama, Kazuo
12 Rawitz, Dror
10 Konrad, Christian
10 Mitra, Pradipta Prometheus
8 Miyazaki, Shuichi
7 Halldórsson, Bjarni V.
7 Patt-Shamir, Boaz
7 Radhakrishnan, Jaikumar
7 Tonoyan, Tigran
6 Gandhi, Rajiv B.
6 Holzer, Stephan
6 Losievskaja, Elena
6 Szegedy, Mario
5 Bar-Noy, Amotz
5 Telle, Jan Arne
4 Boppana, Ravi B.
4 Emek, Yuval
4 Fraigniaud, Pierre
4 Kratochvíl, Jan
4 Rosén, Adi
4 Tokuyama, Takeshi
4 Yanagisawa, Hiroki
3 Akutsu, Tatsuya
3 Bodlaender, Marijke Hans L.
3 Chandra, Barun
3 Kitaev, Sergey
3 Kobayashi, Naoki
3 Köhler, Sven
3 Markatou, Evangelia Anna
3 Morita, Yasufumi
3 Pyatkin, Artem V.
3 Speckmann, Bettina
3 Wang, Yuexuan
3 Wattenhofer, Roger P.
3 Yu, Dongxiao
2 Aceto, Luca
2 Aoki, Yusuke
2 Asgeirsson, Eyjolfur Ingi
2 Bachmann, Unnar Th.
2 Bar-Yehuda, Reuven
2 Damaschke, Peter
2 Damgård, Ivan Bjerre
2 Demetrescu, Camil
2 Epstein, Leah
2 Even, Guy
2 Feige, Uriel
2 Fukunaga, Takuro
2 Goldberg, Leslie Ann
2 Halpern, Joseph Yehuda
2 Hirata, Tomio
2 Ingólfsdóttir, Anna
2 Ito, Takehiro
2 Iwano, Kazuo
2 Kako, Akihisa
2 Katoh, Naoki
2 Levin, Asaf
2 Li, Li Erran
2 Lynch, Nancy Ann
2 Mansour, Yishay
2 Mirrokni, Vahab S.
2 Nagamochi, Hiroshi
2 Naor, Joseph Seffi
2 Ono, Takao
2 Salman, Ravit
2 Shapira, Irina
2 Sviridenko, Maxim I.
2 Taketomi, Shiro
2 Walukiewicz, Igor
2 Zhou, Xiao
1 Arkin, Esther M.
1 Asano, Takao
1 Aspvall, Bengt
1 Bang-Jensen, Jørgen
1 Bellare, Mihir
1 Catanzaro, Daniele
1 Chaplick, Steven
1 Crescenzi, Pierluigi
1 Czumaj, Artur
1 De Bontridder, Koen Margerite Jozef
1 Dinitz, Michael H.
1 Egilsson, Ágúst Sverrir
1 Erlebach, Thomas
1 Felsner, Stefan
1 Fukagawa, Daiji
1 Greenlaw, Raymond
1 Harutyunyan, Hovhannes A.
1 Hassin, Refael
1 Hixon, Thomas
1 Hurkens, Cor A. J.
1 Irving, Robert W.
1 Ishii, Toshimasa
1 Izumi, Taisuke
1 Kajitani, Yoji
1 Kaplan, Lotem
1 Karlsson, Ragnar K.
1 Knauer, Christian
1 Korman, Amos
...and 36 more Co-Authors

Publications by Year

Citations contained in zbMATH

129 Publications have been cited 981 times in 690 Documents Cited by Year
Approximating discrete collections via local improvements. Zbl 0847.90136
Halldórsson, Magnús M.
40
1995
Approximating maximum independent sets by excluding subgraphs. Zbl 0761.68044
Boppana, Ravi; Halldórsson, Magnús M.
39
1992
On chromatic sums and distributed resource allocation. Zbl 0895.68022
Bar-Noy, Amotz; Bellare, Mihir; Halldórsson, Magnús M.; Shachnai, Hadas; Tamir, Tami
37
1998
Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Zbl 0866.68077
Halldórsson, M. M.; Radhakrishnan, J.
35
1997
Coloring powers of planar graphs. Zbl 1029.05047
Agnarsson, Geir; Halldórsson, Magnús M.
34
2003
Approximating the minimum maximal independence number. Zbl 0778.68041
Halldórsson, Magnús M.
33
1993
Scheduling split intervals. Zbl 1111.68046
Bar-Yehuda, R.; Halldórsson, M. M.; Naor, J.; Shachnai, H.; Shapira, I.
32
2006
Approximation algorithms for the test cover problem. Zbl 1160.90646
de Bontridder, K. M. J.; Halldórsson, M. M.; Hurkens, C. A. J.; Lenstra, J. K.; Ravi, R.; Stougie, L.; Halldórsson, B. V.
30
2003
Approximating the domatic number. Zbl 1021.05072
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind
28
2002
Approximations of weighted independent set and hereditary subset problems. Zbl 0952.05069
Halldórsson, Magnús M.
25
2000
A still better performance guarantee for approximate graph coloring. Zbl 0768.68043
Halldórsson, Magnús M.
25
1993
Approximating the tree and tour covers of a graph. Zbl 0785.68041
Arkin, Esther M.; Halldórsson, Magnús M.; Hassin, Refael
23
1993
Scheduling with conflicts: Online and offline algorithms. Zbl 1170.90390
Even, Guy; Halldórsson, Magnús M.; Kaplan, Lotem; Ron, Dana
22
2009
Scheduling split intervals. Zbl 1093.68548
Bar-Yehuda, Reuven; Halldórsson, Magnús M.; Naor, Joseph (Seffi); Shachnai, Hadas; Shapira, Irina
20
2002
Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs. Zbl 1069.68531
Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
16
2003
On powers of chordal graphs and their colorings. Zbl 0976.05027
Agnarsson, Geir; Greenlaw, Raymond; Halldórsson, Magnús M.
16
2000
Coloring powers of planar graphs. Zbl 0965.05042
Agnarsson, Geir; Halldórsson, Magnús M.
16
2000
Wireless communication is in APX. Zbl 1248.68117
Halldórsson, Magnús M.; Wattenhofer, Roger
15
2009
Lower bounds for on-line graph coloring. Zbl 0822.68081
Halldórsson, Magnus M.; Szegedy, Mario
15
1994
Improved approximation results for the stable marriage problem. Zbl 1192.68903
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki Shuichi; Yanagisawa, Hiroki
14
2007
Independent sets with domination constraints. Zbl 0939.05063
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
14
2000
Approximation of independent sets in graphs. Zbl 0903.05044
Halldórsson, Magnús M.
14
1998
Online independent sets. Zbl 1061.68187
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Taketomi, Shiro
12
2002
Approximability results for stable marriage problems with ties. Zbl 1060.68085
Halldórsson, Magnús M.; Irving, Robert W.; Iwama, Kazuo; Manlove, David F.; Miyazaki, Shuichi; Morita, Yasufumi; Scott, Sandy
11
2003
Greedy local improvement and weighted set packing approximation. Zbl 0974.68238
Chandra, Barun; Halldórsson, Magnús M.
11
2001
Wireless capacity with oblivious power in general metrics. Zbl 1373.68157
Halldórsson, Magnús M.; Mitra, Pradipta
10
2011
Multicoloring trees. Zbl 1054.68016
Halldórsson, Magnús M.; Kortsarz, Guy; Proskurowski, Andrzej; Salman, Ravit; Shachnai, Hadas; Telle, Jan Arne
10
2003
On the approximability of the minimum test collection problem (extended abstract). Zbl 1006.68958
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ravi, R.
10
2001
On the impact of identifiers on local decision. Zbl 1323.68032
Fraigniaud, Pierre; Halldórsson, Magnús M.; Korman, Amos
9
2012
Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1333.68077
Halldórsson, Magnús M.; Mitra, Pradipta
9
2011
Randomized approximation of the stable marriage problem. Zbl 1071.68080
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki
9
2004
Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring. Zbl 0891.05061
Halldórsson, Magnús M.; Lau, Hoong Chuin
9
1997
Greed is good: approximating independent sets in sparse and bounded-degree graphs. Zbl 1344.68286
Halldórsson, Magnús; Radhakrishnan, Jaikumar
9
1994
Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Zbl 0817.68088
Halldórsson, Magnús M.; Radhakrishnan, Jaikumar
9
1994
Max point-tolerance graphs. Zbl 1350.05118
Catanzaro, Daniele; Chaplick, Steven; Felsner, Stefan; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Hixon, Thomas; Stacho, Juraj
8
2017
Semi-transitive orientations and word-representable graphs. Zbl 1329.05217
Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem
8
2016
Wireless scheduling with power control. Zbl 1301.68074
Halldórsson, Magnús M.
8
2012
Graphs capturing alternations in words. Zbl 1250.68219
Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem
8
2010
Multicoloring: Problems and techniques. Zbl 1096.68684
Halldórsson, Magnús M.; Kortsarz, Guy
8
2004
Sum multicoloring of graphs. Zbl 0964.68105
Bar-Noy, Amotz; Halldórsson, Magnús M.; Kortsarz, Guy; Salman, Ravit; Shachnai, Hadas
8
2000
Lower bounds for on-line graph coloring. Zbl 0829.68096
Halldórsson, Magnús M.; Szegedy, Márió
8
1992
Online set packing. Zbl 1286.68488
Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror
7
2012
Alternation graphs. Zbl 1341.05243
Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem
7
2011
Robust cost colorings. Zbl 1192.90071
Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi
7
2008
Minimizing interference of a wireless ad-hoc network in a plane. Zbl 1156.68008
Halldórsson, Magnús M.; Tokuyama, Takeshi
7
2008
Batch coloring flat graphs and thin. Zbl 1155.68578
Halldórsson, Magnús M.; Shachnai, Hadas
7
2008
Improved bounds for sum multicoloring and scheduling dependent jobs with minsum criteria. Zbl 1124.90323
Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
7
2005
Tools for multicoloring with applications to planar graphs and partial \(k\)-trees. Zbl 0993.05070
Halldórsson, Magnús M.; Kortsarz, Guy
7
2002
Greedy local improvement and weighted set packing approximation. Zbl 0961.90093
Chandra, Barun; Halldórsson, Magnús M.
7
1999
Parallel and on-line graph coloring. Zbl 0873.68165
Halldórsson, Magnús M.
7
1997
Online set packing and competitive scheduling of multi-part tasks. Zbl 1315.68035
Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror
6
2010
Improved bounds for scheduling conflicting jobs with minsum criteria. Zbl 1446.90078
Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
6
2008
Strip graphs: Recognition and scheduling. Zbl 1167.68409
Halldórsson, Magnús M.; Karlsson, Ragnar K.
6
2006
On colorings of squares of outerplanar graphs. Zbl 1318.05022
Agnarsson, Geir; Halldórsson, Magnús M.
6
2004
Powers of geometric intersection graphs and dispersion algorithms. Zbl 1029.05106
Agnarsson, Geir; Damaschke, Peter; Halldórsson, Magnús M.
6
2003
Approximation algorithms for dispersion problems. Zbl 0974.68153
Chandra, Barun; Halldórsson, Magnús M.
6
2001
Approximating \(k\)-set cover and complementary graph coloring. Zbl 1415.90103
Halldórsson, Magnús M.
6
1996
Vertex coloring edge-weighted digraphs. Zbl 1330.05058
Bang-Jensen, Jørgen; Halldórsson, Magnús M.
5
2015
Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees. Zbl 1258.68102
Akutsu, Tatsuya; Fukagawa, Daiji; Halldórsson, Magnús M.; Takasu, Atsuhiro; Tanaka, Keisuke
5
2013
Wireless scheduling with power control. Zbl 1256.68020
Halldórsson, Magnús M.
5
2009
Strong colorings of hypergraphs. Zbl 1124.05316
Agnarsson, Geir; Halldórsson, Magnús M.
5
2005
Minimizing average completion of dedicated tasks and interval graphs. Zbl 0998.68508
Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
5
2001
Approximating the domatic number. Zbl 1296.05150
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy
5
2000
How well can graphs represent wireless interference? Zbl 1321.68023
Halldorsson, Magnus M.; Tonoyan, Tigran
4
2015
Beyond geometry: towards fully realistic wireless models. Zbl 1321.68457
Bodlaender, Marijke H. L.; Halldorsson, Magnus M.
4
2014
Wireless connectivity and capacity. Zbl 1421.68133
Halldórsson, Magnús M.; Mitra, Pradipta
4
2012
Distributed connectivity of wireless networks. Zbl 1301.68255
Halldórsson, Magnús M.; Mitra, Pradipta
4
2012
Weighted sum coloring in batch scheduling of conflicting jobs. Zbl 1183.68106
Epstein, Leah; Halldórsson, Magnús M.; Levin, Asaf; Shachnai, Hadas
4
2009
Improved approximation of the stable marriage problem. Zbl 1266.05173
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki
4
2003
Inapproximability results on stable marriage problems. Zbl 1059.68578
Halldórsson, Magnús; Iwama, Kazuo; Miyazaki, Shuichi; Morita, Yasufumi
4
2002
Online coloring known graphs. Zbl 0940.05030
Halldórsson, Magnús M.
4
2000
Mod-2 independence and domination in graphs. Zbl 0943.05081
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
4
1999
The power of oblivious wireless power. Zbl 1371.68021
Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta; Wattenhofer, Roger
3
2017
The power of non-uniform wireless power. Zbl 1421.68230
Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta; Wattenhofer, Roger
3
2013
Online scheduling with interval conflicts. Zbl 1310.68253
Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror
3
2013
“Rent-or-buy” scheduling and cost coloring problems. Zbl 1135.90344
Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi
3
2007
Improved results for data migration and open shop scheduling. Zbl 1321.68119
Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
3
2006
Mod-2 independence and domination in graphs. Zbl 1320.05121
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
3
2000
On the approximation of largest common subtrees and largest common point sets. Zbl 0952.68163
Akutsu, Tatsuya; Halldórsson, Magnús M.
3
2000
Approximations of weighted independent set and hereditary subset problems. Zbl 0945.68146
Halldórsson, Magnús M.
3
1999
Finding subsets maximizing minimum structures. Zbl 0848.68071
Halldórsson, Magnús M.; Iwano, Kazuo; Katoh, Naoki; Tokuyama, Takeshi
3
1995
The minimum vulnerability problem on specific graph classes. Zbl 1356.90148
Aoki, Yusuke; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ito, Takehiro; Konrad, Christian; Zhou, Xiao
2
2016
Streaming algorithms for independent sets in sparse hypergraphs. Zbl 1347.68363
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario
2
2016
Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1357.68021
Halldórsson, Magnús M.; Mitra, Pradipta
2
2016
The price of local power control in wireless scheduling. Zbl 1366.68014
Halldórsson, Magnús M.; Tonoyan, Tigran
2
2015
Online selection of intervals and \(t\)-intervals. Zbl 1358.68323
Bachmann, Unnar Th.; Halldórsson, Magnús M.; Shachnai, Hadas
2
2013
SDP-based algorithms for maximum independent set problems on hypergraphs. Zbl 1258.05089
Agnarsson, Geir; Halldórsson, Magnús M.; Losievskaja, Elena
2
2013
Streaming and communication complexity of clique approximation. Zbl 1272.68333
Halldórsson, Magnús M.; Sun, Xiaoming; Szegedy, Mario; Wang, Chengu
2
2012
Sum edge coloring of multigraphs via configuration LP. Zbl 1295.90010
Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim
2
2011
Streaming algorithms for independent sets. Zbl 1288.68189
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario
2
2010
Approximation algorithms for the weighted independent set problem in sparse graphs. Zbl 1173.05352
Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M.
2
2009
Independent sets in bounded-degree hypergraphs. Zbl 1173.05035
Halldórsson, Magnús M.; Losievskaja, Elena
2
2009
Min sum edge coloring in multigraphs via configuration LP. Zbl 1143.90334
Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim
2
2008
Independent sets in bounded-degree hypergraphs. Zbl 1209.05160
Halldórsson, Magnús M.; Losievskaja, Elena
2
2007
Complete partitions of graphs. Zbl 1164.68038
Halldórsson, Magnús M.; Kortsarz, Guy; Radhakrishnan, Jaikumar; Sivasubramanian, Sivaramakrishnan
2
2007
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. Zbl 1182.68361
Czumaj, Artur; Halldórsson, Magnús M.; Lingas, Andrzej; Nilsson, Johan
2
2005
Online independent sets. Zbl 0988.68568
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Taketomi, Shiro
2
2000
Online coloring known graphs. Zbl 0925.68342
Halldórsson, Magnús M.
2
1999
On the approximation of largest common subtrees and largest common point sets. Zbl 0953.68555
Akutsu, Tatsuya; Halldórsson, Magnús M.
2
1994
Computing large independent sets in a single round. Zbl 1423.68340
Halldórsson, Magnús M.; Konrad, Christian
1
2018
Computing large independent sets in a single round. Zbl 1423.68340
Halldórsson, Magnús M.; Konrad, Christian
1
2018
Max point-tolerance graphs. Zbl 1350.05118
Catanzaro, Daniele; Chaplick, Steven; Felsner, Stefan; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Hixon, Thomas; Stacho, Juraj
8
2017
The power of oblivious wireless power. Zbl 1371.68021
Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta; Wattenhofer, Roger
3
2017
Universal framework for wireless scheduling problems. Zbl 1442.68019
Ásgeirsson, Eyjólfur I.; Halldórsson, Magnús M.; Tonoyan, Tigran
1
2017
Semi-transitive orientations and word-representable graphs. Zbl 1329.05217
Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem
8
2016
The minimum vulnerability problem on specific graph classes. Zbl 1356.90148
Aoki, Yusuke; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ito, Takehiro; Konrad, Christian; Zhou, Xiao
2
2016
Streaming algorithms for independent sets in sparse hypergraphs. Zbl 1347.68363
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario
2
2016
Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1357.68021
Halldórsson, Magnús M.; Mitra, Pradipta
2
2016
Brief announcement: Local independent set approximation. Zbl 1376.68156
Bodlaender, Marijke H. L.; Halldórsson, Magnús M.; Konrad, Christian; Kuhn, Fabian
1
2016
Vertex coloring edge-weighted digraphs. Zbl 1330.05058
Bang-Jensen, Jørgen; Halldórsson, Magnús M.
5
2015
How well can graphs represent wireless interference? Zbl 1321.68023
Halldorsson, Magnus M.; Tonoyan, Tigran
4
2015
The price of local power control in wireless scheduling. Zbl 1366.68014
Halldórsson, Magnús M.; Tonoyan, Tigran
2
2015
Distributed large independent sets in one round on bounded-independence graphs. Zbl 1394.68429
Halldórsson, Magnús M.; Konrad, Christian
1
2015
Leveraging multiple channels in ad hoc networks. Zbl 1333.68275
Halldorsson, Magnus M.; Wang, Yuexuan; Yu, Dongxiao
1
2015
A local broadcast layer for the SINR network model. Zbl 1333.68274
Halldórsson, Magnus M.; Holzer, Stephan; Lynch, Nancy
1
2015
Beyond geometry: towards fully realistic wireless models. Zbl 1321.68457
Bodlaender, Marijke H. L.; Halldorsson, Magnus M.
4
2014
Distributed algorithms for coloring interval graphs. Zbl 1437.68196
Halldórsson, Magnús M.; Konrad, Christian
1
2014
Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees. Zbl 1258.68102
Akutsu, Tatsuya; Fukagawa, Daiji; Halldórsson, Magnús M.; Takasu, Atsuhiro; Tanaka, Keisuke
5
2013
The power of non-uniform wireless power. Zbl 1421.68230
Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta; Wattenhofer, Roger
3
2013
Online scheduling with interval conflicts. Zbl 1310.68253
Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror
3
2013
Online selection of intervals and \(t\)-intervals. Zbl 1358.68323
Bachmann, Unnar Th.; Halldórsson, Magnús M.; Shachnai, Hadas
2
2013
SDP-based algorithms for maximum independent set problems on hypergraphs. Zbl 1258.05089
Agnarsson, Geir; Halldórsson, Magnús M.; Losievskaja, Elena
2
2013
Connectivity and aggregation in multihop wireless networks. Zbl 1323.68551
Bodlaender, Marijke H. L.; Halldórsson, Magnús M.; Mitra, Pradipta
1
2013
Shrinking maxima, decreasing costs: new online packing and covering problems. Zbl 1335.68297
Fraigniaud, Pierre; Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror; Rosén, Adi
1
2013
On the impact of identifiers on local decision. Zbl 1323.68032
Fraigniaud, Pierre; Halldórsson, Magnús M.; Korman, Amos
9
2012
Wireless scheduling with power control. Zbl 1301.68074
Halldórsson, Magnús M.
8
2012
Online set packing. Zbl 1286.68488
Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror
7
2012
Wireless connectivity and capacity. Zbl 1421.68133
Halldórsson, Magnús M.; Mitra, Pradipta
4
2012
Distributed connectivity of wireless networks. Zbl 1301.68255
Halldórsson, Magnús M.; Mitra, Pradipta
4
2012
Streaming and communication complexity of clique approximation. Zbl 1272.68333
Halldórsson, Magnús M.; Sun, Xiaoming; Szegedy, Mario; Wang, Chengu
2
2012
Space-constrained interval selection. Zbl 1272.68456
Emek, Yuval; Halldórsson, Magnús M.; Rosén, Adi
1
2012
Wireless capacity with oblivious power in general metrics. Zbl 1373.68157
Halldórsson, Magnús M.; Mitra, Pradipta
10
2011
Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1333.68077
Halldórsson, Magnús M.; Mitra, Pradipta
9
2011
Alternation graphs. Zbl 1341.05243
Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem
7
2011
Sum edge coloring of multigraphs via configuration LP. Zbl 1295.90010
Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim
2
2011
Online scheduling with interval conflicts. Zbl 1230.68054
Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror
1
2011
Algorithms – ESA 2011. 19th annual European symposium, Saarbrücken, Germany, September 5–9, 2011. Proceedings. Zbl 1222.68007
Demetrescu, Camil (ed.); Halldórsson, Magnús M. (ed.)
1
2011
Graphs capturing alternations in words. Zbl 1250.68219
Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem
8
2010
Online set packing and competitive scheduling of multi-part tasks. Zbl 1315.68035
Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror
6
2010
Streaming algorithms for independent sets. Zbl 1288.68189
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario
2
2010
On spectrum sharing games. Zbl 1267.91007
Halldórsson, Magnús M.; Halpern, Joseph Y.; Li, Li Erran; Mirrokni, Vahab S.
1
2010
Online coloring of hypergraphs. Zbl 1229.68082
Halldórsson, Magnús M.
1
2010
Vertex coloring the square of outerplanar graphs of low degree. Zbl 1217.05056
Agnarsson, Geir; Halldórsson, Magnús M.
1
2010
Online selection of intervals and \(t\)-intervals. Zbl 1285.68220
Bachmann, Unnar Th.; Halldórsson, Magnús M.; Shachnai, Hadas
1
2010
Scheduling with conflicts: Online and offline algorithms. Zbl 1170.90390
Even, Guy; Halldórsson, Magnús M.; Kaplan, Lotem; Ron, Dana
22
2009
Wireless communication is in APX. Zbl 1248.68117
Halldórsson, Magnús M.; Wattenhofer, Roger
15
2009
Wireless scheduling with power control. Zbl 1256.68020
Halldórsson, Magnús M.
5
2009
Weighted sum coloring in batch scheduling of conflicting jobs. Zbl 1183.68106
Epstein, Leah; Halldórsson, Magnús M.; Levin, Asaf; Shachnai, Hadas
4
2009
Approximation algorithms for the weighted independent set problem in sparse graphs. Zbl 1173.05352
Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M.
2
2009
Independent sets in bounded-degree hypergraphs. Zbl 1173.05035
Halldórsson, Magnús M.; Losievskaja, Elena
2
2009
SDP-based algorithms for maximum independent set problems on hypergraphs. Zbl 1248.68549
Agnarsson, Geir; Halldórsson, Magnús M.; Losievskaja, Elena
1
2009
Robust cost colorings. Zbl 1192.90071
Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi
7
2008
Minimizing interference of a wireless ad-hoc network in a plane. Zbl 1156.68008
Halldórsson, Magnús M.; Tokuyama, Takeshi
7
2008
Batch coloring flat graphs and thin. Zbl 1155.68578
Halldórsson, Magnús M.; Shachnai, Hadas
7
2008
Improved bounds for scheduling conflicting jobs with minsum criteria. Zbl 1446.90078
Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
6
2008
Min sum edge coloring in multigraphs via configuration LP. Zbl 1143.90334
Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim
2
2008
Vertex coloring acyclic digraphs and their corresponding hypergraphs. Zbl 1152.05324
Agnarsson, Geir; Egilsson, Ágúst S.; Halldórsson, Magnús M.
1
2008
Improved approximation results for the stable marriage problem. Zbl 1192.68903
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki Shuichi; Yanagisawa, Hiroki
14
2007
“Rent-or-buy” scheduling and cost coloring problems. Zbl 1135.90344
Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi
3
2007
Independent sets in bounded-degree hypergraphs. Zbl 1209.05160
Halldórsson, Magnús M.; Losievskaja, Elena
2
2007
Complete partitions of graphs. Zbl 1164.68038
Halldórsson, Magnús M.; Kortsarz, Guy; Radhakrishnan, Jaikumar; Sivasubramanian, Sivaramakrishnan
2
2007
Strongly simplicial vertices of powers of trees. Zbl 1126.05036
Agnarsson, Geir; Halldórsson, Magnús M.
1
2007
Scheduling split intervals. Zbl 1111.68046
Bar-Yehuda, R.; Halldórsson, M. M.; Naor, J.; Shachnai, H.; Shapira, I.
32
2006
Strip graphs: Recognition and scheduling. Zbl 1167.68409
Halldórsson, Magnús M.; Karlsson, Ragnar K.
6
2006
Improved results for data migration and open shop scheduling. Zbl 1321.68119
Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
3
2006
Improved bounds for sum multicoloring and scheduling dependent jobs with minsum criteria. Zbl 1124.90323
Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
7
2005
Strong colorings of hypergraphs. Zbl 1124.05316
Agnarsson, Geir; Halldórsson, Magnús M.
5
2005
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. Zbl 1182.68361
Czumaj, Artur; Halldórsson, Magnús M.; Lingas, Andrzej; Nilsson, Johan
2
2005
Approximation algorithms for the weighted independent set problem. Zbl 1171.68870
Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M.
1
2005
Randomized approximation of the stable marriage problem. Zbl 1071.68080
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki
9
2004
Multicoloring: Problems and techniques. Zbl 1096.68684
Halldórsson, Magnús M.; Kortsarz, Guy
8
2004
On colorings of squares of outerplanar graphs. Zbl 1318.05022
Agnarsson, Geir; Halldórsson, Magnús M.
6
2004
On spectrum sharing games. Zbl 1322.91014
Halldórsson, Magnús M.; Halpern, Joseph Y.; Li, Li (Erran); Mirrokni, Vahab S.
1
2004
Improved results for data migration and open shop scheduling. Zbl 1099.68015
Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
1
2004
Coloring powers of planar graphs. Zbl 1029.05047
Agnarsson, Geir; Halldórsson, Magnús M.
34
2003
Approximation algorithms for the test cover problem. Zbl 1160.90646
de Bontridder, K. M. J.; Halldórsson, M. M.; Hurkens, C. A. J.; Lenstra, J. K.; Ravi, R.; Stougie, L.; Halldórsson, B. V.
30
2003
Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs. Zbl 1069.68531
Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
16
2003
Approximability results for stable marriage problems with ties. Zbl 1060.68085
Halldórsson, Magnús M.; Irving, Robert W.; Iwama, Kazuo; Manlove, David F.; Miyazaki, Shuichi; Morita, Yasufumi; Scott, Sandy
11
2003
Multicoloring trees. Zbl 1054.68016
Halldórsson, Magnús M.; Kortsarz, Guy; Proskurowski, Andrzej; Salman, Ravit; Shachnai, Hadas; Telle, Jan Arne
10
2003
Powers of geometric intersection graphs and dispersion algorithms. Zbl 1029.05106
Agnarsson, Geir; Damaschke, Peter; Halldórsson, Magnús M.
6
2003
Improved approximation of the stable marriage problem. Zbl 1266.05173
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki
4
2003
Randomized approximation of the stable marriage problem. Zbl 1276.68173
Halldórsson, Magnús; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki
1
2003
Approximating the domatic number. Zbl 1021.05072
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind
28
2002
Scheduling split intervals. Zbl 1093.68548
Bar-Yehuda, Reuven; Halldórsson, Magnús M.; Naor, Joseph (Seffi); Shachnai, Hadas; Shapira, Irina
20
2002
Online independent sets. Zbl 1061.68187
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Taketomi, Shiro
12
2002
Tools for multicoloring with applications to planar graphs and partial \(k\)-trees. Zbl 0993.05070
Halldórsson, Magnús M.; Kortsarz, Guy
7
2002
Inapproximability results on stable marriage problems. Zbl 1059.68578
Halldórsson, Magnús; Iwama, Kazuo; Miyazaki, Shuichi; Morita, Yasufumi
4
2002
Greedy local improvement and weighted set packing approximation. Zbl 0974.68238
Chandra, Barun; Halldórsson, Magnús M.
11
2001
On the approximability of the minimum test collection problem (extended abstract). Zbl 1006.68958
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ravi, R.
10
2001
Approximation algorithms for dispersion problems. Zbl 0974.68153
Chandra, Barun; Halldórsson, Magnús M.
6
2001
Minimizing average completion of dedicated tasks and interval graphs. Zbl 0998.68508
Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas
5
2001
Approximations for the general block distribution of a matrix. Zbl 0983.68072
Aspvall, Bengt; Halldórsson, Magnús M.; Manne, Fredrik
1
2001
Approximations of weighted independent set and hereditary subset problems. Zbl 0952.05069
Halldórsson, Magnús M.
25
2000
On powers of chordal graphs and their colorings. Zbl 0976.05027
Agnarsson, Geir; Greenlaw, Raymond; Halldórsson, Magnús M.
16
2000
Coloring powers of planar graphs. Zbl 0965.05042
Agnarsson, Geir; Halldórsson, Magnús M.
16
2000
Independent sets with domination constraints. Zbl 0939.05063
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
14
2000
Sum multicoloring of graphs. Zbl 0964.68105
Bar-Noy, Amotz; Halldórsson, Magnús M.; Kortsarz, Guy; Salman, Ravit; Shachnai, Hadas
8
2000
Approximating the domatic number. Zbl 1296.05150
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy
5
2000
Online coloring known graphs. Zbl 0940.05030
Halldórsson, Magnús M.
4
2000
Mod-2 independence and domination in graphs. Zbl 1320.05121
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
3
2000
...and 29 more Documents
all top 5

Cited by 1,233 Authors

41 Halldórsson, Magnús Mar
28 Paschos, Vangelis Th.
13 Monnot, Jérôme
13 Rawitz, Dror
11 Fernau, Henning
10 Manlove, David F.
9 Demange, Marc
9 Jiang, Minghui
9 Kitaev, Sergey
8 Bazgan, Cristina
8 Henning, Michael Anthony
8 Levin, Asaf
8 Lin, Guohui
8 Miyazaki, Shuichi
7 Cardinal, Jean-Paul
7 Epstein, Leah
7 Escoffier, Bruno
7 Fraigniaud, Pierre
7 Fujito, Toshihiro
7 Iwama, Kazuo
7 Wang, Yuexuan
6 Boudhar, Mourad
6 Feige, Uriel
6 Foucaud, Florent
6 Irving, Robert W.
6 Kortsarz, Guy
6 Král’, Daniel
6 Kratochvíl, Jan
6 Rautenbach, Dieter
6 Shachnai, Hadas
6 Spirakis, Paul G.
6 Valencia-Pabon, Mario E.
6 Wattenhofer, Roger P.
6 Yu, Dongxiao
5 Alon, Noga M.
5 Boyar, Joan F.
5 Branković, Ljiljana
5 Cardoso, Domingos Moreira
5 Fertin, Guillaume
5 Golovach, Petr A.
5 Gutin, Gregory Z.
5 Hermelin, Danny
5 Hua, Qiangsheng
5 Lau, Francis Chi Moon
5 Löwenstein, Christian
5 Marx, Dániel
5 Mestre, Julián
5 Mitra, Pradipta Prometheus
5 Nikoletseas, Sotiris E.
5 Patt-Shamir, Boaz
5 Reichman, Daniel
5 Salavatipour, Mohammad R.
5 van Bevern, René
5 Wang, Jianxin
5 Yeo, Anders
4 Akutsu, Tatsuya
4 Bar-Noy, Amotz
4 Bonomo, Flavia
4 Borodin, Allan B.
4 Borodin, Oleg Veniaminovich
4 Bourgeois, Nicolas
4 Bulteau, Laurent
4 Caragiannis, Ioannis
4 Casel, Katrin
4 Feng, Qilong
4 Fiorini, Samuel
4 Goebel, Randy G.
4 Hassin, Refael
4 Hoefer, Martin
4 Ivanova, Anna Olegovna
4 Joret, Gwenaël
4 Kowalski, Dariusz R.
4 Kratsch, Dieter
4 Lampis, Michael
4 Liedloff, Mathieu
4 Miyano, Eiji
4 Nejedlý, Pavel
4 Niedermeier, Rolf
4 Pach, János
4 Peleg, David
4 Pyatkin, Artem V.
4 Vialette, Stéphane
4 Wang, Lusheng
4 Wu, Weili
4 Yanagisawa, Hiroki
4 Zhu, Binhai
3 Agnarsson, Geir
3 Albers, Susanne
3 Bendraouche, Mohamed
3 Bonnet, Edouard
3 Boria, Nicolas
3 Chaplick, Steven
3 Chen, Jian-er
3 Cranston, Daniel W.
3 Damaschke, Peter
3 de Werra, Dominique
3 Doi, Takashi
3 Edwards, Keith J.
3 Eto, Hiroshi
3 Favrholdt, Lene Monrad
...and 1,133 more Authors
all top 5

Cited in 99 Serials

111 Theoretical Computer Science
78 Discrete Applied Mathematics
43 Algorithmica
34 Information Processing Letters
33 Discrete Mathematics
33 Journal of Combinatorial Optimization
17 Journal of Discrete Algorithms
15 Journal of Computer and System Sciences
13 Theory of Computing Systems
12 European Journal of Operational Research
12 Journal of Scheduling
10 Distributed Computing
9 Information and Computation
9 RAIRO. Operations Research
8 Algorithms
7 Operations Research Letters
7 Graphs and Combinatorics
7 Computers & Operations Research
6 Annals of Operations Research
6 Computational Geometry
6 Discrete Optimization
5 Journal of Graph Theory
5 European Journal of Combinatorics
5 Mathematical Programming. Series A. Series B
4 SIAM Journal on Computing
4 Linear Algebra and its Applications
3 Journal of Combinatorial Theory. Series B
3 Combinatorica
3 Random Structures & Algorithms
3 Journal of Global Optimization
3 Discussiones Mathematicae. Graph Theory
2 Artificial Intelligence
2 Applied Mathematics and Computation
2 Information Sciences
2 SIAM Journal on Discrete Mathematics
2 Journal of Parallel and Distributed Computing
2 Japan Journal of Industrial and Applied Mathematics
2 International Journal of Foundations of Computer Science
2 International Journal of Computer Mathematics
2 Computational Complexity
2 Combinatorics, Probability and Computing
2 The Electronic Journal of Combinatorics
2 International Transactions in Operational Research
2 Journal of Mathematical Chemistry
2 Journal of Graph Algorithms and Applications
2 RAIRO. Theoretical Informatics and Applications
2 4OR
2 Optimization Letters
2 Discrete Mathematics, Algorithms and Applications
2 Acta Universitatis Sapientiae. Informatica
2 Computer Science Review
1 Acta Informatica
1 Computers & Mathematics with Applications
1 Acta Mathematica
1 Advances in Mathematics
1 Automatica
1 BIT
1 Czechoslovak Mathematical Journal
1 International Journal of Game Theory
1 Journal of Algebra
1 Mathematics of Operations Research
1 Networks
1 Quaestiones Mathematicae
1 SIAM Journal on Numerical Analysis
1 Siberian Mathematical Journal
1 Annals of Pure and Applied Logic
1 International Journal of Production Research
1 Order
1 Optimization
1 Journal of Complexity
1 Journal of Computer Science and Technology
1 Discrete & Computational Geometry
1 International Journal of Approximate Reasoning
1 Applied Mathematics Letters
1 Siberian Advances in Mathematics
1 Discrete Mathematics and Applications
1 Games and Economic Behavior
1 Aequationes Mathematicae
1 Journal of Heuristics
1 Constraints
1 INFORMS Journal on Computing
1 Mathematical Problems in Engineering
1 Mathematical Communications
1 Optimization Methods & Software
1 Soft Computing
1 Mathematical Methods of Operations Research
1 Journal of Integer Sequences
1 Acta Mathematica Sinica. English Series
1 JMMA. Journal of Mathematical Modelling and Algorithms
1 Journal of Applied Mathematics and Computing
1 Central European Journal of Mathematics
1 Quantum Information Processing
1 ACM Journal of Experimental Algorithmics
1 AKCE International Journal of Graphs and Combinatorics
1 Journal of Zhejiang University. Science A
1 Symmetry
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
1 Communications in Applied and Industrial Mathematics
1 Journal of Dynamics and Games

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.