Marx, Dániel (ed.) Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. (English) Zbl 1466.68023 Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-646-5/ebook). ix, 3041 p. (2021). MSC: 68-06 68Wxx 00B25 PDFBibTeX XMLCite \textit{D. Marx} (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10--13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (2021; Zbl 1466.68023) Full Text: DOI
Marx, Dániel Chordless cycle packing is fixed-parameter tractable. (English) Zbl 07651210 Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 71, 19 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{D. Marx}, LIPIcs -- Leibniz Int. Proc. Inform. 173, Article 71, 19 p. (2020; Zbl 07651210) Full Text: DOI
Marx, Dániel Four shorts stories on surprising algorithmic uses of treewidth. (English) Zbl 07604209 Fomin, Fedor V. (ed.) et al., Treewidth, kernels, and algorithms. Essays dedicated to Hans L. Bodlaender on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 12160, 129-144 (2020). MSC: 68-XX PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 12160, 129--144 (2020; Zbl 07604209) Full Text: DOI arXiv
Marx, Dániel Tractable hypergraph properties for constraint satisfaction and conjunctive queries. (English) Zbl 1281.68135 J. ACM 60, No. 6, Article No. 42, 51 p. (2013). MSC: 68Q25 90C27 05C65 68R10 PDFBibTeX XMLCite \textit{D. Marx}, J. ACM 60, No. 6, Article No. 42, 51 p. (2013; Zbl 1281.68135) Full Text: DOI
Marx, Dániel Completely inapproximable monotone and antimonotone parameterized problems. (English) Zbl 1261.68066 J. Comput. Syst. Sci. 79, No. 1, 144-151 (2013). MSC: 68Q17 68W25 PDFBibTeX XMLCite \textit{D. Marx}, J. Comput. Syst. Sci. 79, No. 1, 144--151 (2013; Zbl 1261.68066) Full Text: DOI arXiv
Marx, Dániel A tight lower bound for planar multiway cut with fixed number of terminals. (English) Zbl 1272.68147 Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9–13, 2012. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-31593-0/pbk). Lecture Notes in Computer Science 7391, 677-688 (2012). MSC: 68Q17 05C10 05C40 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 7391, 677--688 (2012; Zbl 1272.68147) Full Text: DOI
Marx, Dániel What’s next? Future directions in parameterized complexity. (English) Zbl 1358.68143 Bodlaender, Hans L. (ed.) et al., The multivariate algorithmic revolution and beyond. Essays dedicated to Michael R. Fellows on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-642-30890-1/pbk). Lecture Notes in Computer Science 7370, 469-496 (2012). MSC: 68Q25 01A67 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 7370, 469--496 (2012; Zbl 1358.68143) Full Text: DOI
Marx, Dániel Important separators and parameterized algorithms. (English) Zbl 1341.05212 Kolman, Petr (ed.) et al., Graph-theoretic concepts in computer science. 37th international workshop, WG 2011, Teplá Monastery, Czech Republic, June 21–24, 2011. Revised papers. Berlin: Springer (ISBN 978-3-642-25869-5/pbk). Lecture Notes in Computer Science 6986, 5-10 (2011). MSC: 05C70 05C20 05C85 68Q25 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 6986, 5--10 (2011; Zbl 1341.05212) Full Text: DOI
Marx, Dániel Complexity of clique coloring and related problems. (English) Zbl 1222.05070 Theor. Comput. Sci. 412, No. 29, 3487-3500 (2011). MSC: 05C15 05C69 68Q17 PDFBibTeX XMLCite \textit{D. Marx}, Theor. Comput. Sci. 412, No. 29, 3487--3500 (2011; Zbl 1222.05070) Full Text: DOI
Marx, Dániel Tractable structures for constraint satisfaction with truth tables. (English) Zbl 1253.68180 Theory Comput. Syst. 48, No. 3, 444-464 (2011). MSC: 68Q25 68R10 68Q17 PDFBibTeX XMLCite \textit{D. Marx}, Theory Comput. Syst. 48, No. 3, 444--464 (2011; Zbl 1253.68180) Full Text: DOI Link
Marx, Dániel Approximating fractional hypertree width. (English) Zbl 1300.05201 ACM Trans. Algorithms 6, No. 2, Article No. 29, 17 p. (2010). MSC: 05C65 05C12 05C72 68Q25 68W25 PDFBibTeX XMLCite \textit{D. Marx}, ACM Trans. Algorithms 6, No. 2, Article No. 29, 17 p. (2010; Zbl 1300.05201) Full Text: DOI
Marx, Dániel Tractable hypergraph properties for constraint satisfaction and conjunctive queries. (English) Zbl 1293.68171 Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 735-744 (2010). MSC: 68Q25 05C65 PDFBibTeX XMLCite \textit{D. Marx}, in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC '10. Cambridge, MA, USA, June 5--8, 2010. New York, NY: Association for Computing Machinery (ACM). 735--744 (2010; Zbl 1293.68171) Full Text: DOI
Marx, Dániel Can you beat treewidth? (English) Zbl 1213.68316 Theory Comput. 6, Paper No. 5, 85-112 (2010). MSC: 68Q17 68R10 PDFBibTeX XMLCite \textit{D. Marx}, Theory Comput. 6, Paper No. 5, 85--112 (2010; Zbl 1213.68316) Full Text: DOI
Marx, Dániel Chordal deletion is fixed-parameter tractable. (English) Zbl 1220.05066 Algorithmica 57, No. 4, 747-768 (2010). MSC: 05C38 PDFBibTeX XMLCite \textit{D. Marx}, Algorithmica 57, No. 4, 747--768 (2010; Zbl 1220.05066) Full Text: DOI
Marx, Dániel Approximating fractional hypertree width. (English) Zbl 1423.05113 Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 902-911 (2009). MSC: 05C65 05C12 05C72 68Q25 68W25 PDFBibTeX XMLCite \textit{D. Marx}, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4--6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 902--911 (2009; Zbl 1423.05113) Full Text: Link
Marx, Dániel Tractable structures for constraint satisfaction with truth tables. (English) Zbl 1236.68098 Albers, Susanne (ed.) et al., STACS 2009. 26th international symposium on theoretical aspects of computer science, Freiburg, Germany, February 26–28, 2009. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-09-5). LIPIcs – Leibniz International Proceedings in Informatics 3, 649-660, electronic only (2009). MSC: 68Q17 05C65 05C83 PDFBibTeX XMLCite \textit{D. Marx}, LIPIcs -- Leibniz Int. Proc. Inform. 3, 649--660 (2009; Zbl 1236.68098) Full Text: DOI Link
Marx, Dániel A parameterized view on matroid optimization problems. (English) Zbl 1180.90275 Theor. Comput. Sci. 410, No. 44, 4471-4479 (2009). MSC: 90C27 90C60 PDFBibTeX XMLCite \textit{D. Marx}, Theor. Comput. Sci. 410, No. 44, 4471--4479 (2009; Zbl 1180.90275) Full Text: DOI
Marx, Dániel Complexity results for minimum sum edge coloring. (English) Zbl 1169.05382 Discrete Appl. Math. 157, No. 5, 1034-1045 (2009). MSC: 05C85 68Q25 05C15 PDFBibTeX XMLCite \textit{D. Marx}, Discrete Appl. Math. 157, No. 5, 1034--1045 (2009; Zbl 1169.05382) Full Text: DOI
Marx, Dániel Closest substring problems with small distances. (English) Zbl 1178.68695 SIAM J. Comput. 38, No. 4, 1382-1410 (2008). MSC: 68W32 68Q17 68Q25 PDFBibTeX XMLCite \textit{D. Marx}, SIAM J. Comput. 38, No. 4, 1382--1410 (2008; Zbl 1178.68695) Full Text: DOI Link
Marx, Dániel Complexity of unique list colorability. (English) Zbl 1146.05314 Theor. Comput. Sci. 401, No. 1-3, 62-76 (2008). MSC: 05C85 05C15 68Q15 68R10 PDFBibTeX XMLCite \textit{D. Marx}, Theor. Comput. Sci. 401, No. 1--3, 62--76 (2008; Zbl 1146.05314) Full Text: DOI
Marx, Dániel Searching the \(k\)-change neighborhood for TSP is W[1]-hard. (English) Zbl 1166.90364 Oper. Res. Lett. 36, No. 1, 31-36 (2008). MSC: 90C27 90C35 68Q17 90B40 90C60 90B06 PDFBibTeX XMLCite \textit{D. Marx}, Oper. Res. Lett. 36, No. 1, 31--36 (2008; Zbl 1166.90364) Full Text: DOI
Marx, Dániel Precoloring extension on chordal graphs. (English) Zbl 1123.05041 Bondy, Adrian (ed.) et al., Graph theory in Paris. Proceedings of a conference, GT04, in memory of Claude Berge, Paris, France, July 2004. Basel: Birkhäuser (ISBN 3-7643-7228-1/hbk). Trends in Mathematics, 255-270 (2007). Reviewer: Peter Horák (Tacoma) MSC: 05C15 05C85 PDFBibTeX XMLCite \textit{D. Marx}, in: Graph theory in Paris. Proceedings of a conference, GT04, in memory of Claude Berge, Paris, France, July 2004. Basel: Birkhäuser. 255--270 (2007; Zbl 1123.05041)
Marx, Dániel A parameterized view on matroid optimization problems. (English) Zbl 1223.05016 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 655-666 (2006). MSC: 05B35 68Q25 90C27 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 4051, 655--666 (2006; Zbl 1223.05016) Full Text: DOI
Marx, Dániel Chordal deletion is fixed-parameter tractable. (English) Zbl 1167.68412 Fomin, Fedor V. (ed.), Graph-theoretic concepts in computer science. 32nd international workshop, WG 2006, Bergen, Norway, June 22–24, 2006. Revised papers. Berlin: Springer (ISBN 978-3-540-48381-6/pbk). Lecture Notes in Computer Science 4271, 37-48 (2006). MSC: 68R10 05C85 68Q17 68Q25 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 4271, 37--48 (2006; Zbl 1167.68412) Full Text: DOI Link
Marx, Dániel Parameterized complexity of independence and domination on geometric graphs. (English) Zbl 1154.68431 Bodlaender, Hans L. (ed.) et al., Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-39098-5/pbk). Lecture Notes in Computer Science 4169, 154-165 (2006). MSC: 68Q25 05C62 05C69 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 4169, 154--165 (2006; Zbl 1154.68431) Full Text: DOI
Marx, Dániel Minimum sum multicoloring on the edges of trees. (English) Zbl 1097.68105 Theor. Comput. Sci. 361, No. 2-3, 133-149 (2006). MSC: 68R10 05C15 05C85 68W25 PDFBibTeX XMLCite \textit{D. Marx}, Theor. Comput. Sci. 361, No. 2--3, 133--149 (2006; Zbl 1097.68105) Full Text: DOI
Marx, Dániel Precoloring extension on unit interval graphs. (English) Zbl 1090.05028 Discrete Appl. Math. 154, No. 6, 995-1002 (2006). MSC: 05C15 05C38 PDFBibTeX XMLCite \textit{D. Marx}, Discrete Appl. Math. 154, No. 6, 995--1002 (2006; Zbl 1090.05028) Full Text: DOI
Marx, Dániel Parameterized coloring problems on chordal graphs. (English) Zbl 1087.68072 Theor. Comput. Sci. 351, No. 3, 407-424 (2006). MSC: 68R10 05C15 PDFBibTeX XMLCite \textit{D. Marx}, Theor. Comput. Sci. 351, No. 3, 407--424 (2006; Zbl 1087.68072) Full Text: DOI
Marx, Dániel Parameterized graph separation problems. (English) Zbl 1086.68104 Theor. Comput. Sci. 351, No. 3, 394-406 (2006). MSC: 68R10 68Q25 05C85 PDFBibTeX XMLCite \textit{D. Marx}, Theor. Comput. Sci. 351, No. 3, 394--406 (2006; Zbl 1086.68104) Full Text: DOI
Marx, Dániel The complexity of chromatic strength and chromatic edge strength. (English) Zbl 1103.05032 Comput. Complexity 14, No. 4, 308-340 (2005). MSC: 05C15 05C85 68Q17 68R10 PDFBibTeX XMLCite \textit{D. Marx}, Comput. Complexity 14, No. 4, 308--340 (2005; Zbl 1103.05032) Full Text: DOI
Marx, Dániel Efficient approximation schemes for geometric problems? (English) Zbl 1162.68822 Brodal, Gerth Stølting (ed.) et al., Algorithms – ESA 2005. 13th annual European symposium, Palma de Mallorca, Spain, October 3–6, 2005. Proceedings. Berlin: Springer (ISBN 3-540-29118-0/pbk). Lecture Notes in Computer Science 3669, 448-459 (2005). MSC: 68W25 68Q25 68U05 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 3669, 448--459 (2005; Zbl 1162.68822) Full Text: DOI
Marx, Dániel Parameterized complexity of constraint satisfaction problems. (English) Zbl 1085.68068 Comput. Complexity 14, No. 2, 153-183 (2005). MSC: 68Q25 68Q17 68T20 PDFBibTeX XMLCite \textit{D. Marx}, Comput. Complexity 14, No. 2, 153--183 (2005; Zbl 1085.68068) Full Text: DOI
Marx, Dániel Minimum sum multicoloring on the edges of planar graphs and partial \(k\)-trees (extended abstract). (English) Zbl 1124.68374 Persiano, Giuseppe (ed.) et al., Approximation and online algorithms. Second international workshop, WAOA 2004, Bergen, Norway, September 14–16, 2004. Revised selected papers. Berlin: Springer (ISBN 3-540-24574-X/pbk). Lecture Notes in Computer Science 3351, 9-22 (2005). MSC: 68Q25 05C85 68W25 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 3351, 9--22 (2005; Zbl 1124.68374) Full Text: DOI
Marx, Dániel NP-completeness of list coloring and precoloring extension on the edges of planar graphs. (English) Zbl 1068.05024 J. Graph Theory 49, No. 4, 313-324 (2005). MSC: 05C15 68R10 PDFBibTeX XMLCite \textit{D. Marx}, J. Graph Theory 49, No. 4, 313--324 (2005; Zbl 1068.05024) Full Text: DOI
Marx, Dániel A short proof of the NP-completeness of minimum sum interval coloring. (English) Zbl 1067.05027 Oper. Res. Lett. 33, No. 4, 382-384 (2005). MSC: 05C15 68Q17 90C60 PDFBibTeX XMLCite \textit{D. Marx}, Oper. Res. Lett. 33, No. 4, 382--384 (2005; Zbl 1067.05027) Full Text: DOI
Marx, Dániel Minimum sum multicoloring on the edges of trees. (English) Zbl 1213.68467 Jansen, Klaus (ed.) et al., Approximation and online algorithms. First international workshop, WAOA 2003, Budapest, Hungary, September 16–18, 2003. Revised papers. Berlin: Springer (ISBN 3-540-21079-2/pbk). Lecture Notes in Computer Science 2909, 214-226 (2004). MSC: 68R10 05C15 05C85 68W25 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 2909, 214--226 (2004; Zbl 1213.68467) Full Text: DOI
Marx, Dániel List edge multicoloring in graphs with few cycles. (English) Zbl 1183.68433 Inf. Process. Lett. 89, No. 2, 85-90 (2004). MSC: 68R10 68W05 PDFBibTeX XMLCite \textit{D. Marx}, Inf. Process. Lett. 89, No. 2, 85--90 (2004; Zbl 1183.68433) Full Text: DOI
Marx, Dániel Parameterized coloring problems on chordal graphs. (English) Zbl 1104.68544 Downey, Rod (ed.) et al., Parametrized and exact computation. First international workshop, IWPEC 2004, Bergen, Norway, September 14–17, 2004. Proceedings. Berlin: Springer (ISBN 3-540-23071-8/pbk). Lecture Notes in Computer Science 3162, 83-95 (2004). MSC: 68R10 05C15 68Q25 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 3162, 83--95 (2004; Zbl 1104.68544) Full Text: DOI
Marx, Dániel Parameterized graph separation problems. (English) Zbl 1104.68543 Downey, Rod (ed.) et al., Parametrized and exact computation. First international workshop, IWPEC 2004, Bergen, Norway, September 14–17, 2004. Proceedings. Berlin: Springer (ISBN 3-540-23071-8/pbk). Lecture Notes in Computer Science 3162, 71-82 (2004). MSC: 68R10 05C85 68Q25 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 3162, 71--82 (2004; Zbl 1104.68543) Full Text: DOI
Marx, Dániel Eulerian disjoint paths problem in grid graphs is NP-complete. (English) Zbl 1053.05078 Discrete Appl. Math. 143, No. 1-3, 336-341 (2004). MSC: 05C45 05C38 68R10 68Q17 PDFBibTeX XMLCite \textit{D. Marx}, Discrete Appl. Math. 143, No. 1--3, 336--341 (2004; Zbl 1053.05078) Full Text: DOI
Marx, Dániel The complexity of tree multicolorings. (English) Zbl 1014.68117 Diks, Krzysztof (ed.) et al., Mathematical foundations of computer science 2002. 27th symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2420, 532-542 (2002). MSC: 68R10 68Q17 05C15 PDFBibTeX XMLCite \textit{D. Marx}, Lect. Notes Comput. Sci. 2420, 532--542 (2002; Zbl 1014.68117) Full Text: Link