Edit Profile (opens in new tab) Halldórsson, Magnús Mar Compute Distance To: Compute Author ID: halldorsson.magnus-m Published as: Halldórsson, Magnús M.; Halldorsson, Magnus M.; Halldórsson, Magnús; Halldórsson, M. M.; Halldórsson, Magnus M.; Halldórsson, Magnus Homepage: https://www.ru.is/~mmh/ External Links: MGP · ORCID · Google Scholar · dblp Documents Indexed: 177 Publications since 1992 13 Contributions as Editor Co-Authors: 142 Co-Authors with 172 Joint Publications 4,355 Co-Co-Authors all top 5 Co-Authors 18 single-authored 22 Kortsarz, Guy 17 Shachnai, Hadas 14 Tonoyan, Tigran 13 Agnarsson, Geir 12 Iwama, Kazuo 12 Mitra, Pradipta Prometheus 12 Rawitz, Dror 10 Konrad, Christian 8 Halldórsson, Bjarni V. 8 Miyazaki, Shuichi 7 Patt-Shamir, Boaz 7 Radhakrishnan, Jaikumar 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 Wattenhofer, Roger P. 4 Yanagisawa, Hiroki 3 Akutsu, Tatsuya 3 Bodlaender, Marijke Hans L. 3 Chandra, Barun 3 Chaplick, Steven 3 Kitaev, Sergey 3 Kobayashi, Naoki 3 Köhler, Sven 3 Markatou, Evangelia Anna 3 Morita, Yasufumi 3 Pyatkin, Artem V. 3 Ravi, Ramamoorthi 3 Speckmann, Bettina 3 Wang, Yuexuan 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 De Bontridder, Koen Margerite Jozef 2 de Lima, Murilo Santos 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 Hurkens, Cor A. J. 2 Ingólfsdóttir, Anna 2 Ishii, Toshimasa 2 Ito, Takehiro 2 Iwano, Kazuo 2 Kako, Akihisa 2 Katoh, Naoki 2 Kuhn, Fabian 2 Lenstra, Jan Karel 2 Levin, Asaf 2 Li, Li Erran 2 Lynch, Nancy Ann 2 Makino, Kazuhisa 2 Mansour, Yishay 2 Mirrokni, Vahab S. 2 Nagamochi, Hiroshi 2 Naor, Joseph Seffi 2 Ono, Takao 2 Salman, Ravit 2 Shapira, Irina 2 Stougie, Leen 2 Sviridenko, Maxim I. 2 Takazawa, Kenjiro 2 Taketomi, Shiro 2 Walukiewicz, Igor 2 Zhou, Xiao 1 Arkin, Esther M. 1 Arnþórsson, Ívar Marrow 1 Asano, Takao 1 Aspvall, Bengt 1 Bang-Jensen, Jørgen 1 Bellare, Mihir 1 Catanzaro, Daniele 1 Crescenzi, Pierluigi 1 Cygan, Marek 1 Czumaj, Artur 1 Dinitz, Michael H. 1 Egilsson, Ágúst Sverrir 1 Erlebach, Thomas 1 Felsner, Stefan 1 Fukagawa, Daiji 1 Greenlaw, Raymond 1 Gylfason, Jökull Snær ...and 42 more Co-Authors all top 5 Serials 19 Theoretical Computer Science 9 Lecture Notes in Computer Science 8 Discrete Applied Mathematics 8 Information Processing Letters 8 Algorithmica 8 ACM Transactions on Algorithms 6 Distributed Computing 5 SIAM Journal on Computing 5 Journal of Algorithms 4 Information and Computation 2 SIAM Journal on Discrete Mathematics 2 Journal of Graph Algorithms and Applications 2 RIMS Kokyuroku 1 Discrete Mathematics 1 BIT 1 Networks 1 Operations Research Letters 1 Combinatorica 1 International Journal of Foundations of Computer Science 1 Mathematical Programming. Series A. Series B 1 Congressus Numerantium 1 Nordic Journal of Computing 1 The Electronic Journal of Combinatorics 1 Discussiones Mathematicae. Graph Theory 1 Theory of Computing Systems 1 Journal of Combinatorial Optimization 1 Journal of Scheduling all top 5 Fields 164 Computer science (68-XX) 84 Combinatorics (05-XX) 33 Operations research, mathematical programming (90-XX) 13 General and overarching topics; collections (00-XX) 7 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 7 Information and communication theory, circuits (94-XX) 2 Biology and other natural sciences (92-XX) 1 Order, lattices, ordered algebraic structures (06-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 134 Publications have been cited 1,055 times in 754 Documents Cited by ▼ Year ▼ Approximating discrete collections via local improvements. Zbl 0847.90136Halldórsson, Magnús M. 41 1995 Approximating maximum independent sets by excluding subgraphs. Zbl 0761.68044Boppana, Ravi; Halldórsson, Magnús M. 41 1992 On chromatic sums and distributed resource allocation. Zbl 0895.68022Bar-Noy, Amotz; Bellare, Mihir; Halldórsson, Magnús M.; Shachnai, Hadas; Tamir, Tami 37 1998 Scheduling split intervals. Zbl 1111.68046Bar-Yehuda, R.; Halldórsson, M. M.; Naor, J.; Shachnai, H.; Shapira, I. 36 2006 Coloring powers of planar graphs. Zbl 1029.05047Agnarsson, Geir; Halldórsson, Magnús M. 36 2003 Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Zbl 0866.68077Halldórsson, M. M.; Radhakrishnan, J. 35 1997 Approximation algorithms for the test cover problem. Zbl 1160.90646de Bontridder, K. M. J.; Halldórsson, M. M.; Hurkens, C. A. J.; Lenstra, J. K.; Ravi, R.; Stougie, L.; Halldórsson, B. V. 34 2003 Approximating the minimum maximal independence number. Zbl 0778.68041Halldórsson, Magnús M. 34 1993 Approximating the domatic number. Zbl 1021.05072Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind 28 2002 Approximations of weighted independent set and hereditary subset problems. Zbl 0952.05069Halldórsson, Magnús M. 28 2000 Scheduling with conflicts: Online and offline algorithms. Zbl 1170.90390Even, Guy; Halldórsson, Magnús M.; Kaplan, Lotem; Ron, Dana 27 2009 A still better performance guarantee for approximate graph coloring. Zbl 0768.68043Halldórsson, Magnús M. 25 1993 Approximating the tree and tour covers of a graph. Zbl 0785.68041Arkin, Esther M.; Halldórsson, Magnús M.; Hassin, Refael 22 1993 Scheduling split intervals. Zbl 1093.68548Bar-Yehuda, Reuven; Halldórsson, Magnús M.; Naor, Joseph (Seffi); Shachnai, Hadas; Shapira, Irina 21 2002 Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs. Zbl 1069.68531Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 19 2003 Wireless communication is in APX. Zbl 1248.68117Halldórsson, Magnús M.; Wattenhofer, Roger 16 2009 On powers of chordal graphs and their colorings. Zbl 0976.05027Agnarsson, Geir; Greenlaw, Raymond; Halldórsson, Magnús M. 16 2000 Coloring powers of planar graphs. Zbl 0965.05042Agnarsson, Geir; Halldórsson, Magnús M. 16 2000 Lower bounds for on-line graph coloring. Zbl 0822.68081Halldórsson, Magnus M.; Szegedy, Mario 16 1994 Independent sets with domination constraints. Zbl 0939.05063Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne 15 2000 Greedy local improvement and weighted set packing approximation. Zbl 0974.68238Chandra, Barun; Halldórsson, Magnús M. 13 2001 Improved approximation results for the stable marriage problem. Zbl 1192.68903Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki Shuichi; Yanagisawa, Hiroki 13 2007 Max point-tolerance graphs. Zbl 1350.05118Catanzaro, Daniele; Chaplick, Steven; Felsner, Stefan; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Hixon, Thomas; Stacho, Juraj 13 2017 Online independent sets. Zbl 1061.68187Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Taketomi, Shiro 12 2002 Approximation of independent sets in graphs. Zbl 0903.05044Halldórsson, Magnús M. 12 1998 Approximability results for stable marriage problems with ties. Zbl 1060.68085Halldórsson, Magnús M.; Irving, Robert W.; Iwama, Kazuo; Manlove, David F.; Miyazaki, Shuichi; Morita, Yasufumi; Scott, Sandy 12 2003 Graphs capturing alternations in words. Zbl 1250.68219Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 12 2010 Wireless capacity with oblivious power in general metrics. Zbl 1373.68157Halldórsson, Magnús M.; Mitra, Pradipta 12 2011 On the approximability of the minimum test collection problem (extended abstract). Zbl 1006.68958Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ravi, R. 11 2001 Wireless scheduling with power control. Zbl 1301.68074Halldórsson, Magnús M. 10 2012 Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring. Zbl 0891.05061Halldórsson, Magnús M.; Lau, Hoong Chuin 10 1997 Multicoloring trees. Zbl 1054.68016Halldórsson, Magnús M.; Kortsarz, Guy; Proskurowski, Andrzej; Salman, Ravit; Shachnai, Hadas; Telle, Jan Arne 10 2003 Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Zbl 0817.68088Halldórsson, Magnús M.; Radhakrishnan, Jaikumar 10 1994 Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1333.68077Halldórsson, Magnús M.; Mitra, Pradipta 9 2011 Randomized approximation of the stable marriage problem. Zbl 1071.68080Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki 9 2004 Lower bounds for on-line graph coloring. Zbl 0829.68096Halldórsson, Magnús M.; Szegedy, Márió 9 1992 On the impact of identifiers on local decision. Zbl 1323.68032Fraigniaud, Pierre; Halldórsson, Magnús M.; Korman, Amos 9 2012 Semi-transitive orientations and word-representable graphs. Zbl 1329.05217Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 9 2016 Greed is good: approximating independent sets in sparse and bounded-degree graphs. Zbl 1344.68286Halldórsson, Magnús; Radhakrishnan, Jaikumar 9 1994 Parallel and on-line graph coloring. Zbl 0873.68165Halldórsson, Magnús M. 8 1997 Multicoloring: Problems and techniques. Zbl 1096.68684Halldórsson, Magnús M.; Kortsarz, Guy 8 2004 Alternation graphs. Zbl 1341.05243Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 8 2011 Online set packing. Zbl 1286.68488Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror 8 2012 Approximation algorithms for dispersion problems. Zbl 0974.68153Chandra, Barun; Halldórsson, Magnús M. 8 2001 Minimizing interference of a wireless ad-hoc network in a plane. Zbl 1156.68008Halldórsson, Magnús M.; Tokuyama, Takeshi 8 2008 Sum multicoloring of graphs. Zbl 0964.68105Bar-Noy, Amotz; Halldórsson, Magnús M.; Kortsarz, Guy; Salman, Ravit; Shachnai, Hadas 8 2000 Improved bounds for scheduling conflicting jobs with minsum criteria. Zbl 1446.90078Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 7 2008 Tools for multicoloring with applications to planar graphs and partial \(k\)-trees. Zbl 0993.05070Halldórsson, Magnús M.; Kortsarz, Guy 7 2002 Greedy local improvement and weighted set packing approximation. Zbl 0961.90093Chandra, Barun; Halldórsson, Magnús M. 7 1999 Powers of geometric intersection graphs and dispersion algorithms. Zbl 1029.05106Agnarsson, Geir; Damaschke, Peter; Halldórsson, Magnús M. 7 2003 Batch coloring flat graphs and thin. Zbl 1155.68578Halldórsson, Magnús M.; Shachnai, Hadas 7 2008 Robust cost colorings. Zbl 1192.90071Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi 7 2008 Approximating \(k\)-set cover and complementary graph coloring. Zbl 1415.90103Halldórsson, Magnús M. 7 1996 Beyond geometry: towards fully realistic wireless models. Zbl 1321.68457Bodlaender, Marijke H. L.; Halldorsson, Magnus M. 7 2014 Online set packing and competitive scheduling of multi-part tasks. Zbl 1315.68035Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror 6 2010 Wireless connectivity and capacity. Zbl 1421.68133Halldórsson, Magnús M.; Mitra, Pradipta 6 2012 Strong colorings of hypergraphs. Zbl 1124.05316Agnarsson, Geir; Halldórsson, Magnús M. 6 2005 Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees. Zbl 1258.68102Akutsu, Tatsuya; Fukagawa, Daiji; Halldórsson, Magnús M.; Takasu, Atsuhiro; Tanaka, Keisuke 6 2013 Strip graphs: Recognition and scheduling. Zbl 1167.68409Halldórsson, Magnús M.; Karlsson, Ragnar K. 6 2006 On colorings of squares of outerplanar graphs. Zbl 1318.05022Agnarsson, Geir; Halldórsson, Magnús M. 6 2004 How well can graphs represent wireless interference? Zbl 1321.68023Halldorsson, Magnus M.; Tonoyan, Tigran 6 2015 Approximating the domatic number. Zbl 1296.05150Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy 6 2000 Minimizing average completion of dedicated tasks and interval graphs. Zbl 0998.68508Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 5 2001 Improved bounds for sum multicoloring and scheduling dependent jobs with minsum criteria. Zbl 1124.90323Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 5 2005 Vertex coloring edge-weighted digraphs. Zbl 1330.05058Bang-Jensen, Jørgen; Halldórsson, Magnús M. 5 2015 Improved approximation of the stable marriage problem. Zbl 1266.05173Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki 4 2003 Inapproximability results on stable marriage problems. Zbl 1059.68578Halldórsson, Magnús; Iwama, Kazuo; Miyazaki, Shuichi; Morita, Yasufumi 4 2002 Independent sets in bounded-degree hypergraphs. Zbl 1173.05035Halldórsson, Magnús M.; Losievskaja, Elena 4 2009 Approximations of weighted independent set and hereditary subset problems. Zbl 0945.68146Halldórsson, Magnús M. 4 1999 Online coloring known graphs. Zbl 0940.05030Halldórsson, Magnús M. 4 2000 Mod-2 independence and domination in graphs. Zbl 1320.05121Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne 4 2000 Weighted sum coloring in batch scheduling of conflicting jobs. Zbl 1183.68106Epstein, Leah; Halldórsson, Magnús M.; Levin, Asaf; Shachnai, Hadas 4 2009 Wireless scheduling with power control. Zbl 1256.68020Halldórsson, Magnús M. 4 2009 The power of non-uniform wireless power. Zbl 1421.68230Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta; Wattenhofer, Roger 3 2013 Finding subsets maximizing minimum structures. Zbl 0848.68071Halldórsson, Magnús M.; Iwano, Kazuo; Katoh, Naoki; Tokuyama, Takeshi 3 1995 Online scheduling with interval conflicts. Zbl 1310.68253Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror 3 2013 Approximation algorithms for the weighted independent set problem in sparse graphs. Zbl 1173.05352Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M. 3 2009 Mod-2 independence and domination in graphs. Zbl 0943.05081Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne 3 1999 On the approximation of largest common subtrees and largest common point sets. Zbl 0952.68163Akutsu, Tatsuya; Halldórsson, Magnús M. 3 2000 Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1357.68021Halldórsson, Magnús M.; Mitra, Pradipta 3 2016 Improved results for data migration and open shop scheduling. Zbl 1321.68119Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 3 2006 Sum edge coloring of multigraphs via configuration LP. Zbl 1295.90010Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim 3 2011 “Rent-or-buy” scheduling and cost coloring problems. Zbl 1135.90344Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi 3 2007 The power of oblivious wireless power. Zbl 1371.68021Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta; Wattenhofer, Roger 3 2017 The price of local power control in wireless scheduling. Zbl 1366.68014Halldórsson, Magnús M.; Tonoyan, Tigran 3 2015 Universal framework for wireless scheduling problems. Zbl 1442.68019Ásgeirsson, Eyjólfur I.; Halldórsson, Magnús M.; Tonoyan, Tigran 3 2017 Streaming and communication complexity of clique approximation. Zbl 1272.68333Halldórsson, Magnús M.; Sun, Xiaoming; Szegedy, Mario; Wang, Chengu 2 2012 Distributed connectivity of wireless networks. Zbl 1301.68255Halldórsson, Magnús M.; Mitra, Pradipta 2 2012 Min sum edge coloring in multigraphs via configuration LP. Zbl 1143.90334Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim 2 2008 Online coloring known graphs. Zbl 0925.68342Halldórsson, Magnús M. 2 1999 Online selection of intervals and \(t\)-intervals. Zbl 1358.68323Bachmann, Unnar Th.; Halldórsson, Magnús M.; Shachnai, Hadas 2 2013 SDP-based algorithms for maximum independent set problems on hypergraphs. Zbl 1258.05089Agnarsson, Geir; Halldórsson, Magnús M.; Losievskaja, Elena 2 2013 Independent sets in bounded-degree hypergraphs. Zbl 1209.05160Halldórsson, Magnús M.; Losievskaja, Elena 2 2007 Online independent sets. Zbl 0988.68568Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Taketomi, Shiro 2 2000 Streaming algorithms for independent sets. Zbl 1288.68189Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario 2 2010 On the approximation of largest common subtrees and largest common point sets. Zbl 0953.68555Akutsu, Tatsuya; Halldórsson, Magnús M. 2 1994 Streaming algorithms for independent sets in sparse hypergraphs. Zbl 1347.68363Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario 2 2016 The minimum vulnerability problem on specific graph classes. Zbl 1356.90148Aoki, Yusuke; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ito, Takehiro; Konrad, Christian; Zhou, Xiao 2 2016 A local broadcast layer for the SINR network model. Zbl 1333.68274Halldórsson, Magnus M.; Holzer, Stephan; Lynch, Nancy 2 2015 Query-competitive sorting with uncertainty. Zbl 1462.68031Halldórsson, Magnús M.; de Lima, Murilo Santos 2 2021 Query-competitive sorting with uncertainty. Zbl 1462.68031Halldórsson, Magnús M.; de Lima, Murilo Santos 2 2021 Computing inductive vertex orderings. Zbl 1476.05154Halldórsson, Magnús M.; Tonoyan, Tigran 1 2021 Sparse backbone and optimal distributed SINR algorithms. Zbl 07475096Halldórsson, Magnús M.; Tonoyan, Tigran 1 2021 Radio aggregation scheduling. Zbl 1455.68138Gandhi, Rajiv; Halldórsson, Magnús M.; Konrad, Christian; Kortsarz, Guy; Oh, Hoon 1 2020 Limitations of current wireless link scheduling algorithms. Zbl 1455.68037Halldórsson, Magnús M.; Konrad, Christian; Tonoyan, Tigran 1 2020 Computing large independent sets in a single round. Zbl 1423.68340Halldórsson, Magnús M.; Konrad, Christian 1 2018 Simple and local independent set approximation. Zbl 07008450Boppana, Ravi B.; Halldórsson, Magnús M.; Rawitz, Dror 1 2018 Spanning trees with edge conflicts and wireless connectivity. Zbl 07376085Halldórsson, Magnús M.; Kortsarz, Guy; Mitra, Pradipta; Tonoyan, Tigran 1 2018 Max point-tolerance graphs. Zbl 1350.05118Catanzaro, Daniele; Chaplick, Steven; Felsner, Stefan; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Hixon, Thomas; Stacho, Juraj 13 2017 The power of oblivious wireless power. Zbl 1371.68021Halldó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 3 2017 Posimodular function optimization. Zbl 06778727Halldórsson, Magnús M.; Ishii, Toshimasa; Makino, Kazuhisa; Takazawa, Kenjiro 1 2017 Semi-transitive orientations and word-representable graphs. Zbl 1329.05217Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 9 2016 Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1357.68021Halldórsson, Magnús M.; Mitra, Pradipta 3 2016 Streaming algorithms for independent sets in sparse hypergraphs. Zbl 1347.68363Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario 2 2016 The minimum vulnerability problem on specific graph classes. Zbl 1356.90148Aoki, Yusuke; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ito, Takehiro; Konrad, Christian; Zhou, Xiao 2 2016 Brief announcement: Local independent set approximation. Zbl 1376.68156Bodlaender, Marijke H. L.; Halldórsson, Magnús M.; Konrad, Christian; Kuhn, Fabian 1 2016 Brief announcement: Data dissemination in unified dynamic wireless networks. Zbl 1373.68049Halldórsson, Magnus M.; Tonoyan, Tigran; Wang, Yuexuan; Yu, Dongxiao 1 2016 How well can graphs represent wireless interference? Zbl 1321.68023Halldorsson, Magnus M.; Tonoyan, Tigran 6 2015 Vertex coloring edge-weighted digraphs. Zbl 1330.05058Bang-Jensen, Jørgen; Halldórsson, Magnús M. 5 2015 The price of local power control in wireless scheduling. Zbl 1366.68014Halldórsson, Magnús M.; Tonoyan, Tigran 3 2015 A local broadcast layer for the SINR network model. Zbl 1333.68274Halldórsson, Magnus M.; Holzer, Stephan; Lynch, Nancy 2 2015 Distributed large independent sets in one round on bounded-independence graphs. Zbl 1394.68429Halldórsson, Magnús M.; Konrad, Christian 1 2015 Leveraging multiple channels in ad hoc networks. Zbl 1333.68275Halldorsson, Magnus M.; Wang, Yuexuan; Yu, Dongxiao 1 2015 Beyond geometry: towards fully realistic wireless models. Zbl 1321.68457Bodlaender, Marijke H. L.; Halldorsson, Magnus M. 7 2014 Distributed algorithms for coloring interval graphs. Zbl 1437.68196Halldórsson, Magnús M.; Konrad, Christian 1 2014 Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees. Zbl 1258.68102Akutsu, Tatsuya; Fukagawa, Daiji; Halldórsson, Magnús M.; Takasu, Atsuhiro; Tanaka, Keisuke 6 2013 The power of non-uniform wireless power. Zbl 1421.68230Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta; Wattenhofer, Roger 3 2013 Online scheduling with interval conflicts. Zbl 1310.68253Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror 3 2013 Online selection of intervals and \(t\)-intervals. Zbl 1358.68323Bachmann, Unnar Th.; Halldórsson, Magnús M.; Shachnai, Hadas 2 2013 SDP-based algorithms for maximum independent set problems on hypergraphs. Zbl 1258.05089Agnarsson, Geir; Halldórsson, Magnús M.; Losievskaja, Elena 2 2013 Connectivity and aggregation in multihop wireless networks. Zbl 1323.68551Bodlaender, Marijke H. L.; Halldórsson, Magnús M.; Mitra, Pradipta 1 2013 Shrinking maxima, decreasing costs: new online packing and covering problems. Zbl 1335.68297Fraigniaud, Pierre; Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror; Rosén, Adi 1 2013 Wireless scheduling with power control. Zbl 1301.68074Halldórsson, Magnús M. 10 2012 On the impact of identifiers on local decision. Zbl 1323.68032Fraigniaud, Pierre; Halldórsson, Magnús M.; Korman, Amos 9 2012 Online set packing. Zbl 1286.68488Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror 8 2012 Wireless connectivity and capacity. Zbl 1421.68133Halldórsson, Magnús M.; Mitra, Pradipta 6 2012 Streaming and communication complexity of clique approximation. Zbl 1272.68333Halldórsson, Magnús M.; Sun, Xiaoming; Szegedy, Mario; Wang, Chengu 2 2012 Distributed connectivity of wireless networks. Zbl 1301.68255Halldórsson, Magnús M.; Mitra, Pradipta 2 2012 Wireless capacity with oblivious power in general metrics. Zbl 1373.68157Halldórsson, Magnús M.; Mitra, Pradipta 12 2011 Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1333.68077Halldórsson, Magnús M.; Mitra, Pradipta 9 2011 Alternation graphs. Zbl 1341.05243Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 8 2011 Sum edge coloring of multigraphs via configuration LP. Zbl 1295.90010Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim 3 2011 Online scheduling with interval conflicts. Zbl 1230.68054Halldó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 1 2011 Graphs capturing alternations in words. Zbl 1250.68219Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 12 2010 Online set packing and competitive scheduling of multi-part tasks. Zbl 1315.68035Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror 6 2010 Streaming algorithms for independent sets. Zbl 1288.68189Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario 2 2010 Online selection of intervals and \(t\)-intervals. Zbl 1285.68220Bachmann, Unnar Th.; Halldórsson, Magnús M.; Shachnai, Hadas 1 2010 Vertex coloring the square of outerplanar graphs of low degree. Zbl 1217.05056Agnarsson, Geir; Halldórsson, Magnús M. 1 2010 Online coloring of hypergraphs. Zbl 1229.68082Halldórsson, Magnús M. 1 2010 On spectrum sharing games. Zbl 1267.91007Halldórsson, Magnús M.; Halpern, Joseph Y.; Li, Li Erran; Mirrokni, Vahab S. 1 2010 Scheduling with conflicts: Online and offline algorithms. Zbl 1170.90390Even, Guy; Halldórsson, Magnús M.; Kaplan, Lotem; Ron, Dana 27 2009 Wireless communication is in APX. Zbl 1248.68117Halldórsson, Magnús M.; Wattenhofer, Roger 16 2009 Independent sets in bounded-degree hypergraphs. Zbl 1173.05035Halldórsson, Magnús M.; Losievskaja, Elena 4 2009 Weighted sum coloring in batch scheduling of conflicting jobs. Zbl 1183.68106Epstein, Leah; Halldórsson, Magnús M.; Levin, Asaf; Shachnai, Hadas 4 2009 Wireless scheduling with power control. Zbl 1256.68020Halldórsson, Magnús M. 4 2009 Approximation algorithms for the weighted independent set problem in sparse graphs. Zbl 1173.05352Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M. 3 2009 SDP-based algorithms for maximum independent set problems on hypergraphs. Zbl 1248.68549Agnarsson, Geir; Halldórsson, Magnús M.; Losievskaja, Elena 1 2009 Minimizing interference of a wireless ad-hoc network in a plane. Zbl 1156.68008Halldórsson, Magnús M.; Tokuyama, Takeshi 8 2008 Improved bounds for scheduling conflicting jobs with minsum criteria. Zbl 1446.90078Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 7 2008 Batch coloring flat graphs and thin. Zbl 1155.68578Halldórsson, Magnús M.; Shachnai, Hadas 7 2008 Robust cost colorings. Zbl 1192.90071Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi 7 2008 Min sum edge coloring in multigraphs via configuration LP. Zbl 1143.90334Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim 2 2008 Vertex coloring acyclic digraphs and their corresponding hypergraphs. Zbl 1152.05324Agnarsson, Geir; Egilsson, Ágúst S.; Halldórsson, Magnús M. 1 2008 Improved approximation results for the stable marriage problem. Zbl 1192.68903Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki Shuichi; Yanagisawa, Hiroki 13 2007 “Rent-or-buy” scheduling and cost coloring problems. Zbl 1135.90344Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi 3 2007 Independent sets in bounded-degree hypergraphs. Zbl 1209.05160Halldórsson, Magnús M.; Losievskaja, Elena 2 2007 Complete partitions of graphs. Zbl 1164.68038Halldórsson, Magnús M.; Kortsarz, Guy; Radhakrishnan, Jaikumar; Sivasubramanian, Sivaramakrishnan 1 2007 Strongly simplicial vertices of powers of trees. Zbl 1126.05036Agnarsson, Geir; Halldórsson, Magnús M. 1 2007 Scheduling split intervals. Zbl 1111.68046Bar-Yehuda, R.; Halldórsson, M. M.; Naor, J.; Shachnai, H.; Shapira, I. 36 2006 Strip graphs: Recognition and scheduling. Zbl 1167.68409Halldórsson, Magnús M.; Karlsson, Ragnar K. 6 2006 Improved results for data migration and open shop scheduling. Zbl 1321.68119Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 3 2006 Strong colorings of hypergraphs. Zbl 1124.05316Agnarsson, Geir; Halldórsson, Magnús M. 6 2005 Improved bounds for sum multicoloring and scheduling dependent jobs with minsum criteria. Zbl 1124.90323Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 5 2005 Approximation algorithms for the weighted independent set problem. Zbl 1171.68870Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M. 1 2005 Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. Zbl 1182.68361Czumaj, Artur; Halldórsson, Magnús M.; Lingas, Andrzej; Nilsson, Johan 1 2005 Randomized approximation of the stable marriage problem. Zbl 1071.68080Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki 9 2004 Multicoloring: Problems and techniques. Zbl 1096.68684Halldórsson, Magnús M.; Kortsarz, Guy 8 2004 On colorings of squares of outerplanar graphs. Zbl 1318.05022Agnarsson, Geir; Halldórsson, Magnús M. 6 2004 On spectrum sharing games. Zbl 1322.91014Halldórsson, Magnús M.; Halpern, Joseph Y.; Li, Li (Erran); Mirrokni, Vahab S. 1 2004 Coloring powers of planar graphs. Zbl 1029.05047Agnarsson, Geir; Halldórsson, Magnús M. 36 2003 Approximation algorithms for the test cover problem. Zbl 1160.90646de Bontridder, K. M. J.; Halldórsson, M. M.; Hurkens, C. A. J.; Lenstra, J. K.; Ravi, R.; Stougie, L.; Halldórsson, B. V. 34 2003 Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs. Zbl 1069.68531Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 19 2003 Approximability results for stable marriage problems with ties. Zbl 1060.68085Halldórsson, Magnús M.; Irving, Robert W.; Iwama, Kazuo; Manlove, David F.; Miyazaki, Shuichi; Morita, Yasufumi; Scott, Sandy 12 2003 Multicoloring trees. Zbl 1054.68016Halldó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.05106Agnarsson, Geir; Damaschke, Peter; Halldórsson, Magnús M. 7 2003 Improved approximation of the stable marriage problem. Zbl 1266.05173Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki 4 2003 Randomized approximation of the stable marriage problem. Zbl 1276.68173Halldórsson, Magnús; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki 1 2003 Approximating the domatic number. Zbl 1021.05072Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind 28 2002 Scheduling split intervals. Zbl 1093.68548Bar-Yehuda, Reuven; Halldórsson, Magnús M.; Naor, Joseph (Seffi); Shachnai, Hadas; Shapira, Irina 21 2002 Online independent sets. Zbl 1061.68187Halldó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.05070Halldórsson, Magnús M.; Kortsarz, Guy 7 2002 Inapproximability results on stable marriage problems. Zbl 1059.68578Halldórsson, Magnús; Iwama, Kazuo; Miyazaki, Shuichi; Morita, Yasufumi 4 2002 Greedy local improvement and weighted set packing approximation. Zbl 0974.68238Chandra, Barun; Halldórsson, Magnús M. 13 2001 On the approximability of the minimum test collection problem (extended abstract). Zbl 1006.68958Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ravi, R. 11 2001 Approximation algorithms for dispersion problems. Zbl 0974.68153Chandra, Barun; Halldórsson, Magnús M. 8 2001 Minimizing average completion of dedicated tasks and interval graphs. Zbl 0998.68508Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 5 2001 Approximations for the general block distribution of a matrix. Zbl 0983.68072Aspvall, Bengt; Halldórsson, Magnús M.; Manne, Fredrik 1 2001 Approximations of weighted independent set and hereditary subset problems. Zbl 0952.05069Halldórsson, Magnús M. 28 2000 ...and 34 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 1,326 Authors 48 Halldórsson, Magnús Mar 29 Paschos, Vangelis Th. 13 Monnot, Jérôme 13 Rawitz, Dror 11 Fernau, Henning 11 Kitaev, Sergey 10 Lin, Guohui 10 Manlove, David F. 9 Demange, Marc 9 Henning, Michael Anthony 9 Jiang, Minghui 8 Bazgan, Cristina 7 Epstein, Leah 7 Escoffier, Bruno 7 Foucaud, Florent 7 Fraigniaud, Pierre 7 Fujito, Toshihiro 7 Levin, Asaf 7 Miyazaki, Shuichi 7 Shachnai, Hadas 7 Tonoyan, Tigran 7 Zhu, Binhai 6 Boudhar, Mourad 6 Feige, Uriel 6 Irving, Robert W. 6 Iwama, Kazuo 6 Kortsarz, Guy 6 Kowalski, Dariusz R. 6 Král’, Daniel 6 Kratochvíl, Jan 6 Mitra, Pradipta Prometheus 6 Rautenbach, Dieter 6 Salavatipour, Mohammad R. 6 Spirakis, Paul G. 6 Valencia-Pabon, Mario E. 6 van Bevern, René 6 Wang, Yuexuan 6 Yeo, Anders 6 Yu, Dongxiao 5 Akutsu, Tatsuya 5 Boyar, Joan F. 5 Branković, Ljiljana 5 Cardoso, Domingos Moreira 5 Chaplick, Steven 5 Fertin, Guillaume 5 Goebel, Randy G. 5 Golovach, Petr A. 5 Gutin, Gregory Z. 5 Hermelin, Danny 5 Lampis, Michael 5 Löwenstein, Christian 5 Marx, Dániel 5 Mestre, Julián 5 Nikoletseas, Sotiris E. 5 Patt-Shamir, Boaz 5 Pyatkin, Artem V. 5 Reichman, Daniel 5 Saurabh, Saket 5 Wang, Jianxin 5 Wang, Lusheng 5 Wattenhofer, Roger P. 4 Albers, Susanne 4 Alon, Noga M. 4 Bonomo-Braberman, Flavia 4 Borodin, Allan B. 4 Borodin, Oleg Veniaminovich 4 Bourgeois, Nicolas 4 Bulteau, Laurent 4 Caragiannis, Ioannis 4 Cardinal, Jean 4 Casel, Katrin 4 Feng, Qilong 4 Fiorini, Samuel 4 Hassin, Refael 4 Hoefer, Martin 4 Hua, Qiangsheng 4 Ivanova, Anna Olegovna 4 Joret, Gwenaël 4 Katz, Matthew J. 4 Kratsch, Dieter 4 Lau, Francis Chi Moon 4 Liedloff, Mathieu 4 Maheshwari, Anil 4 Mishra, Sounaka 4 Miyano, Eiji 4 Nejedlý, Pavel 4 Niedermeier, Rolf 4 Pach, János 4 Peleg, David 4 Telle, Jan Arne 4 Vialette, Stéphane 4 Wu, Weili 3 Agnarsson, Geir 3 Bar-Noy, Amotz 3 Bendraouche, Mohamed 3 Bonnet, Edouard 3 Boria, Nicolas 3 Bu, Yuehua 3 Chen, Jian-er 3 Cranston, Daniel W. ...and 1,226 more Authors all top 5 Cited in 111 Serials 114 Theoretical Computer Science 81 Discrete Applied Mathematics 50 Algorithmica 37 Journal of Combinatorial Optimization 35 Information Processing Letters 34 Discrete Mathematics 16 European Journal of Operational Research 16 Journal of Discrete Algorithms 15 Theory of Computing Systems 14 Journal of Computer and System Sciences 12 Distributed Computing 12 Journal of Scheduling 9 Information and Computation 9 Computers & Operations Research 9 RAIRO. Operations Research 8 Operations Research Letters 8 Algorithms 7 Graphs and Combinatorics 7 Annals of Operations Research 7 Computational Geometry 7 The Electronic Journal of Combinatorics 6 Discrete Optimization 5 Journal of Graph Theory 5 SIAM Journal on Computing 5 European Journal of Combinatorics 5 Mathematical Programming. Series A. Series B 4 Linear Algebra and its Applications 3 Applied Mathematics and Computation 3 Journal of Combinatorial Theory. Series B 3 Combinatorica 3 SIAM Journal on Discrete Mathematics 3 Random Structures & Algorithms 3 Journal of Global Optimization 3 Journal of Mathematical Chemistry 3 Discrete Mathematics, Algorithms and Applications 2 Artificial Intelligence 2 Information Sciences 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 Discussiones Mathematicae. Graph Theory 2 International Transactions in Operational Research 2 Mathematical Problems in Engineering 2 RAIRO. Theoretical Informatics and Applications 2 4OR 2 AKCE International Journal of Graphs and Combinatorics 2 Optimization Letters 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 Journal of Combinatorial Theory. Series A 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 Neural Computation 1 Siberian Advances in Mathematics 1 Discrete Mathematics and Applications 1 Games and Economic Behavior 1 Aequationes Mathematicae 1 Georgian Mathematical Journal 1 Top 1 Journal of Heuristics 1 Constraints 1 INFORMS Journal on Computing 1 Mathematical Communications 1 Optimization Methods & Software 1 Soft Computing 1 Mathematical Methods of Operations Research 1 Journal of Graph Algorithms and Applications 1 Annals of Combinatorics 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 Journal of Integer Sequences 1 Acta Mathematica Sinica. English Series 1 Bulletin of the Malaysian Mathematical Sciences Society. Second 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 ...and 11 more Serials all top 5 Cited in 18 Fields 475 Computer science (68-XX) 411 Combinatorics (05-XX) 211 Operations research, mathematical programming (90-XX) 43 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 28 Biology and other natural sciences (92-XX) 10 Information and communication theory, circuits (94-XX) 7 Numerical analysis (65-XX) 5 Convex and discrete geometry (52-XX) 4 Probability theory and stochastic processes (60-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Statistics (62-XX) 2 Mathematical logic and foundations (03-XX) 2 Nonassociative rings and algebras (17-XX) 2 Quantum theory (81-XX) 1 Commutative algebra (13-XX) 1 Algebraic topology (55-XX) 1 Optics, electromagnetic theory (78-XX) 1 Systems theory; control (93-XX) Citations by Year