Edit Profile Halldórsson, Magnús Mar Compute Distance To: Compute Author ID: halldorsson.magnus-m 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 all top 5 Serials 17 Theoretical Computer Science 9 Lecture Notes in Computer Science 8 Discrete Applied Mathematics 7 Information Processing Letters 7 ACM Transactions on Algorithms 6 Algorithmica 6 Distributed Computing 5 Journal of Algorithms 4 SIAM Journal on Computing 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 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 151 Computer science (68-XX) 80 Combinatorics (05-XX) 32 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 129 Publications have been cited 981 times in 690 Documents Cited by ▼ Year ▼ Approximating discrete collections via local improvements. Zbl 0847.90136Halldórsson, Magnús M. 40 1995 Approximating maximum independent sets by excluding subgraphs. Zbl 0761.68044Boppana, Ravi; Halldórsson, Magnús M. 39 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 Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Zbl 0866.68077Halldórsson, M. M.; Radhakrishnan, J. 35 1997 Coloring powers of planar graphs. Zbl 1029.05047Agnarsson, Geir; Halldórsson, Magnús M. 34 2003 Approximating the minimum maximal independence number. Zbl 0778.68041Halldórsson, Magnús M. 33 1993 Scheduling split intervals. Zbl 1111.68046Bar-Yehuda, R.; Halldórsson, M. M.; Naor, J.; Shachnai, H.; Shapira, I. 32 2006 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. 30 2003 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. 25 2000 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 23 1993 Scheduling with conflicts: Online and offline algorithms. Zbl 1170.90390Even, Guy; Halldórsson, Magnús M.; Kaplan, Lotem; Ron, Dana 22 2009 Scheduling split intervals. Zbl 1093.68548Bar-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.68531Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 16 2003 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 Wireless communication is in APX. Zbl 1248.68117Halldórsson, Magnús M.; Wattenhofer, Roger 15 2009 Lower bounds for on-line graph coloring. Zbl 0822.68081Halldórsson, Magnus M.; Szegedy, Mario 15 1994 Improved approximation results for the stable marriage problem. Zbl 1192.68903Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki Shuichi; Yanagisawa, Hiroki 14 2007 Independent sets with domination constraints. Zbl 0939.05063Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne 14 2000 Approximation of independent sets in graphs. Zbl 0903.05044Halldórsson, Magnús M. 14 1998 Online independent sets. Zbl 1061.68187Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Taketomi, Shiro 12 2002 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 11 2003 Greedy local improvement and weighted set packing approximation. Zbl 0974.68238Chandra, Barun; Halldórsson, Magnús M. 11 2001 Wireless capacity with oblivious power in general metrics. Zbl 1373.68157Halldórsson, Magnús M.; Mitra, Pradipta 10 2011 Multicoloring trees. Zbl 1054.68016Halldó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.68958Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Ravi, R. 10 2001 On the impact of identifiers on local decision. Zbl 1323.68032Fraigniaud, Pierre; Halldórsson, Magnús M.; Korman, Amos 9 2012 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 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 9 1997 Greed is good: approximating independent sets in sparse and bounded-degree graphs. Zbl 1344.68286Halldórsson, Magnús; Radhakrishnan, Jaikumar 9 1994 Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Zbl 0817.68088Halldórsson, Magnús M.; Radhakrishnan, Jaikumar 9 1994 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 8 2017 Semi-transitive orientations and word-representable graphs. Zbl 1329.05217Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 8 2016 Wireless scheduling with power control. Zbl 1301.68074Halldórsson, Magnús M. 8 2012 Graphs capturing alternations in words. Zbl 1250.68219Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 8 2010 Multicoloring: Problems and techniques. Zbl 1096.68684Halldórsson, Magnús M.; Kortsarz, Guy 8 2004 Sum multicoloring of graphs. Zbl 0964.68105Bar-Noy, Amotz; Halldórsson, Magnús M.; Kortsarz, Guy; Salman, Ravit; Shachnai, Hadas 8 2000 Lower bounds for on-line graph coloring. Zbl 0829.68096Halldórsson, Magnús M.; Szegedy, Márió 8 1992 Online set packing. Zbl 1286.68488Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror 7 2012 Alternation graphs. Zbl 1341.05243Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 7 2011 Robust cost colorings. Zbl 1192.90071Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi 7 2008 Minimizing interference of a wireless ad-hoc network in a plane. Zbl 1156.68008Halldórsson, Magnús M.; Tokuyama, Takeshi 7 2008 Batch coloring flat graphs and thin. Zbl 1155.68578Halldórsson, Magnús M.; Shachnai, Hadas 7 2008 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 7 2005 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 Parallel and on-line graph coloring. Zbl 0873.68165Halldórsson, Magnús M. 7 1997 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 Improved bounds for scheduling conflicting jobs with minsum criteria. Zbl 1446.90078Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 6 2008 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 Powers of geometric intersection graphs and dispersion algorithms. Zbl 1029.05106Agnarsson, Geir; Damaschke, Peter; Halldórsson, Magnús M. 6 2003 Approximation algorithms for dispersion problems. Zbl 0974.68153Chandra, Barun; Halldórsson, Magnús M. 6 2001 Approximating \(k\)-set cover and complementary graph coloring. Zbl 1415.90103Halldórsson, Magnús M. 6 1996 Vertex coloring edge-weighted digraphs. Zbl 1330.05058Bang-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.68102Akutsu, Tatsuya; Fukagawa, Daiji; Halldórsson, Magnús M.; Takasu, Atsuhiro; Tanaka, Keisuke 5 2013 Wireless scheduling with power control. Zbl 1256.68020Halldórsson, Magnús M. 5 2009 Strong colorings of hypergraphs. Zbl 1124.05316Agnarsson, Geir; Halldórsson, Magnús M. 5 2005 Minimizing average completion of dedicated tasks and interval graphs. Zbl 0998.68508Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 5 2001 Approximating the domatic number. Zbl 1296.05150Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy 5 2000 How well can graphs represent wireless interference? Zbl 1321.68023Halldorsson, Magnus M.; Tonoyan, Tigran 4 2015 Beyond geometry: towards fully realistic wireless models. Zbl 1321.68457Bodlaender, Marijke H. L.; Halldorsson, Magnus M. 4 2014 Wireless connectivity and capacity. Zbl 1421.68133Halldórsson, Magnús M.; Mitra, Pradipta 4 2012 Distributed connectivity of wireless networks. Zbl 1301.68255Halldórsson, Magnús M.; Mitra, Pradipta 4 2012 Weighted sum coloring in batch scheduling of conflicting jobs. Zbl 1183.68106Epstein, Leah; Halldórsson, Magnús M.; Levin, Asaf; Shachnai, Hadas 4 2009 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 Online coloring known graphs. Zbl 0940.05030Halldórsson, Magnús M. 4 2000 Mod-2 independence and domination in graphs. Zbl 0943.05081Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne 4 1999 The power of oblivious wireless power. Zbl 1371.68021Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta; Wattenhofer, Roger 3 2017 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 “Rent-or-buy” scheduling and cost coloring problems. Zbl 1135.90344Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi 3 2007 Improved results for data migration and open shop scheduling. Zbl 1321.68119Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 3 2006 Mod-2 independence and domination in graphs. Zbl 1320.05121Halldó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.68163Akutsu, Tatsuya; Halldórsson, Magnús M. 3 2000 Approximations of weighted independent set and hereditary subset problems. Zbl 0945.68146Halldórsson, Magnús M. 3 1999 Finding subsets maximizing minimum structures. Zbl 0848.68071Halldórsson, Magnús M.; Iwano, Kazuo; Katoh, Naoki; Tokuyama, Takeshi 3 1995 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 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 Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1357.68021Halldórsson, Magnús M.; Mitra, Pradipta 2 2016 The price of local power control in wireless scheduling. Zbl 1366.68014Halldórsson, Magnús M.; Tonoyan, Tigran 2 2015 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 Streaming and communication complexity of clique approximation. Zbl 1272.68333Halldórsson, Magnús M.; Sun, Xiaoming; Szegedy, Mario; Wang, Chengu 2 2012 Sum edge coloring of multigraphs via configuration LP. Zbl 1295.90010Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim 2 2011 Streaming algorithms for independent sets. Zbl 1288.68189Halldó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.05352Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M. 2 2009 Independent sets in bounded-degree hypergraphs. Zbl 1173.05035Halldórsson, Magnús M.; Losievskaja, Elena 2 2009 Min sum edge coloring in multigraphs via configuration LP. Zbl 1143.90334Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim 2 2008 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 2 2007 Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. Zbl 1182.68361Czumaj, Artur; Halldórsson, Magnús M.; Lingas, Andrzej; Nilsson, Johan 2 2005 Online independent sets. Zbl 0988.68568Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Taketomi, Shiro 2 2000 Online coloring known graphs. Zbl 0925.68342Halldórsson, Magnús M. 2 1999 On the approximation of largest common subtrees and largest common point sets. Zbl 0953.68555Akutsu, Tatsuya; Halldórsson, Magnús M. 2 1994 Computing large independent sets in a single round. Zbl 1423.68340Halldórsson, Magnús M.; Konrad, Christian 1 2018 Computing large independent sets in a single round. Zbl 1423.68340Halldórsson, Magnús M.; Konrad, Christian 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 8 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 1 2017 Semi-transitive orientations and word-representable graphs. Zbl 1329.05217Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 8 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 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 Nearly optimal bounds for distributed wireless scheduling in the SINR model. Zbl 1357.68021Halldórsson, Magnús M.; Mitra, Pradipta 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 Vertex coloring edge-weighted digraphs. Zbl 1330.05058Bang-Jensen, Jørgen; Halldórsson, Magnús M. 5 2015 How well can graphs represent wireless interference? Zbl 1321.68023Halldorsson, Magnus M.; Tonoyan, Tigran 4 2015 The price of local power control in wireless scheduling. Zbl 1366.68014Halldórsson, Magnús M.; Tonoyan, Tigran 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 A local broadcast layer for the SINR network model. Zbl 1333.68274Halldórsson, Magnus M.; Holzer, Stephan; Lynch, Nancy 1 2015 Beyond geometry: towards fully realistic wireless models. Zbl 1321.68457Bodlaender, Marijke H. L.; Halldorsson, Magnus M. 4 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 5 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 On the impact of identifiers on local decision. Zbl 1323.68032Fraigniaud, Pierre; Halldórsson, Magnús M.; Korman, Amos 9 2012 Wireless scheduling with power control. Zbl 1301.68074Halldórsson, Magnús M. 8 2012 Online set packing. Zbl 1286.68488Emek, Yuval; Halldórsson, Magnús M.; Mansour, Yishay; Patt-Shamir, Boaz; Radhakrishnan, Jaikumar; Rawitz, Dror 7 2012 Wireless connectivity and capacity. Zbl 1421.68133Halldórsson, Magnús M.; Mitra, Pradipta 4 2012 Distributed connectivity of wireless networks. Zbl 1301.68255Halldórsson, Magnús M.; Mitra, Pradipta 4 2012 Streaming and communication complexity of clique approximation. Zbl 1272.68333Halldórsson, Magnús M.; Sun, Xiaoming; Szegedy, Mario; Wang, Chengu 2 2012 Space-constrained interval selection. Zbl 1272.68456Emek, Yuval; Halldórsson, Magnús M.; Rosén, Adi 1 2012 Wireless capacity with oblivious power in general metrics. Zbl 1373.68157Halldórsson, Magnús M.; Mitra, Pradipta 10 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 7 2011 Sum edge coloring of multigraphs via configuration LP. Zbl 1295.90010Halldórsson, Magnús M.; Kortsarz, Guy; Sviridenko, Maxim 2 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.68007Demetrescu, Camil (ed.); Halldórsson, Magnús M. (ed.) 1 2011 Graphs capturing alternations in words. Zbl 1250.68219Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem 8 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 On spectrum sharing games. Zbl 1267.91007Halldórsson, Magnús M.; Halpern, Joseph Y.; Li, Li Erran; Mirrokni, Vahab S. 1 2010 Online coloring of hypergraphs. Zbl 1229.68082Halldórsson, Magnús M. 1 2010 Vertex coloring the square of outerplanar graphs of low degree. Zbl 1217.05056Agnarsson, Geir; Halldórsson, Magnús M. 1 2010 Online selection of intervals and \(t\)-intervals. Zbl 1285.68220Bachmann, Unnar Th.; Halldórsson, Magnús M.; Shachnai, Hadas 1 2010 Scheduling with conflicts: Online and offline algorithms. Zbl 1170.90390Even, Guy; Halldórsson, Magnús M.; Kaplan, Lotem; Ron, Dana 22 2009 Wireless communication is in APX. Zbl 1248.68117Halldórsson, Magnús M.; Wattenhofer, Roger 15 2009 Wireless scheduling with power control. Zbl 1256.68020Halldórsson, Magnús M. 5 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 Approximation algorithms for the weighted independent set problem in sparse graphs. Zbl 1173.05352Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M. 2 2009 Independent sets in bounded-degree hypergraphs. Zbl 1173.05035Halldórsson, Magnús M.; Losievskaja, Elena 2 2009 SDP-based algorithms for maximum independent set problems on hypergraphs. Zbl 1248.68549Agnarsson, Geir; Halldórsson, Magnús M.; Losievskaja, Elena 1 2009 Robust cost colorings. Zbl 1192.90071Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi 7 2008 Minimizing interference of a wireless ad-hoc network in a plane. Zbl 1156.68008Halldórsson, Magnús M.; Tokuyama, Takeshi 7 2008 Batch coloring flat graphs and thin. Zbl 1155.68578Halldórsson, Magnús M.; Shachnai, Hadas 7 2008 Improved bounds for scheduling conflicting jobs with minsum criteria. Zbl 1446.90078Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 6 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 14 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 2 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. 32 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 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 7 2005 Strong colorings of hypergraphs. Zbl 1124.05316Agnarsson, Geir; Halldórsson, Magnús M. 5 2005 Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. Zbl 1182.68361Czumaj, Artur; Halldórsson, Magnús M.; Lingas, Andrzej; Nilsson, Johan 2 2005 Approximation algorithms for the weighted independent set problem. Zbl 1171.68870Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M. 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 Improved results for data migration and open shop scheduling. Zbl 1099.68015Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas 1 2004 Coloring powers of planar graphs. Zbl 1029.05047Agnarsson, Geir; Halldórsson, Magnús M. 34 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. 30 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 16 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 11 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. 6 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 20 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. 11 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. 10 2001 Approximation algorithms for dispersion problems. Zbl 0974.68153Chandra, Barun; Halldórsson, Magnús M. 6 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. 25 2000 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 Independent sets with domination constraints. Zbl 0939.05063Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne 14 2000 Sum multicoloring of graphs. Zbl 0964.68105Bar-Noy, Amotz; Halldórsson, Magnús M.; Kortsarz, Guy; Salman, Ravit; Shachnai, Hadas 8 2000 Approximating the domatic number. Zbl 1296.05150Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy 5 2000 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 3 2000 ...and 29 more Documents all cited Publications top 5 cited Publications 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 all top 5 Cited in 16 Fields 442 Computer science (68-XX) 370 Combinatorics (05-XX) 191 Operations research, mathematical programming (90-XX) 40 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 26 Biology and other natural sciences (92-XX) 11 Information and communication theory, circuits (94-XX) 7 Numerical analysis (65-XX) 5 Convex and discrete geometry (52-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Probability theory and stochastic processes (60-XX) 2 Mathematical logic and foundations (03-XX) 2 Statistics (62-XX) 1 Nonassociative rings and algebras (17-XX) 1 Optics, electromagnetic theory (78-XX) 1 Quantum theory (81-XX) 1 Systems theory; control (93-XX) 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.