Edit Profile (opens in new tab) Polishchuk, Valentin Compute Distance To: Compute Author ID: polishchuk.valentin Published as: Polishchuk, Valentin External Links: MGP Documents Indexed: 45 Publications since 2006 1 Contribution as Editor Co-Authors: 68 Co-Authors with 46 Joint Publications 1,922 Co-Co-Authors all top 5 Co-Authors 0 single-authored 24 Mitchell, Joseph S. B. 12 Arkin, Esther M. 7 Kostitsyna, Irina 7 Suomela, Jukka 6 Efrat, Alon 6 Sysikaski, Mikko 5 Löffler, Maarten 4 Fekete, Sándor P. 4 Knauer, Christian 4 Schlipf, Lena 4 Wang, Haitao 3 Bae, Sang Won 3 Bender, Michael A. 3 Eriksson-Bique, Sylvester 3 Staals, Frank 3 Talvitie, Topi 3 Yang, Shang 2 Dieckmann, Claudia 2 Floréen, Patrik 2 Kim, Joondong 2 Korman, Matias 2 Krasnoshchekov, Dmitry N. 2 Kröller, Alexander 2 Okamoto, Yoshio 2 Rote, Günter 2 Schmidt, Christiane 2 Vihavainen, Arto 1 Alt, Helmut 1 Åstrand, Matti 1 Daescu, Ovidiu 1 Dror, Moshe 1 Evans, William S. 1 Friedrichs, Stephan 1 Gaddehosur, Poornananda R. 1 Golovin, Daniel 1 Goyal, Vineet 1 Hart, George William 1 Hassinen, Marja 1 Hershberger, John E. 1 Hurtado, Ferran 1 Islam, Kamrul 1 Kaasinen, Joel 1 Kaski, Petteri 1 Kirkpatrick, David G. 1 Kranakis, Evangelos Konstantinou 1 Lee, Yusin 1 Liberatore, Vincenzo 1 Malik, Hemant 1 Meijer, Henk G. 1 Nöllenburg, Martin 1 Núñez-Rodríguez, Yurai 1 Okamoto, Kazuya 1 Orlin, James B. 1 Rappaport, David 1 Ravi, Ramamoorthi 1 Rybicki, Joel 1 Schulz, André 1 Sedov, Leonid 1 Speckmann, Bettina 1 Strash, Darren 1 Suri, Subhash 1 Uitto, Jara 1 van Garderen, Mereke 1 Verbeek, Kevin 1 Wiese, Andreas 1 Xiao, Henry 1 Yildiz, Hakan 1 Zou, Jingyu all top 5 Serials 8 Computational Geometry 4 Information Processing Letters 2 Theoretical Computer Science 2 Algorithmica 2 Theory of Computing Systems 2 Journal of Computational Geometry 1 Discrete Applied Mathematics 1 Discrete & Computational Geometry 1 International Journal of Computational Geometry & Applications 1 Mathematical Programming. Series A. Series B 1 ACM Transactions on Algorithms all top 5 Fields 37 Computer science (68-XX) 11 Operations research, mathematical programming (90-XX) 10 Combinatorics (05-XX) 10 Numerical analysis (65-XX) 3 Convex and discrete geometry (52-XX) 2 General and overarching topics; collections (00-XX) 1 Geometry (51-XX) 1 Differential geometry (53-XX) 1 Mechanics of particles and systems (70-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Systems theory; control (93-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 35 Publications have been cited 110 times in 87 Documents Cited by ▼ Year ▼ Geometric stable roommates. Zbl 1191.68753Arkin, Esther M.; Bae, Sang Won; Efrat, Alon; Okamoto, Kazuya; Mitchell, Joseph S. B.; Polishchuk, Valentin 10 2009 Not being (super)thin or solid is hard: A study of grid Hamiltonicity. Zbl 1193.05105Arkin, Esther M.; Fekete, Sándor P.; Islam, Kamrul; Meijer, Henk; Mitchell, Joseph S. B.; Núñez-Rodríguez, Yurai; Polishchuk, Valentin; Rappaport, David; Xiao, Henry 9 2009 Minimum-link paths revisited. Zbl 1290.65016Mitchell, Joseph S. B.; Polishchuk, Valentin; Sysikaski, Mikko 7 2014 A simple local 3-approximation algorithm for vertex cover. Zbl 1214.68468Polishchuk, Valentin; Suomela, Jukka 6 2009 A local 2-approximation algorithm for the vertex cover problem. Zbl 1261.68161Åstrand, Matti; Floréen, Patrik; Polishchuk, Valentin; Rybicki, Joel; Suomela, Jukka; Uitto, Jara 6 2009 Minimum-perimeter enclosures. Zbl 1186.68509Mitchell, Joseph S. B.; Polishchuk, Valentin 6 2008 Thick non-crossing paths and minimum-cost flows in polygonal domains. Zbl 1221.68277Polishchuk, Valentin; Mitchell, Joseph S. B. 6 2007 Convex transversals. Zbl 1281.65027Arkin, Esther M.; Dieckmann, Claudia; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Schlipf, Lena; Yang, Shang 5 2014 Almost stable matchings by truncating the Gale-Shapley algorithm. Zbl 1204.68144Floréen, Patrik; Kaski, Petteri; Polishchuk, Valentin; Suomela, Jukka 5 2010 Improved approximation algorithms for relay placement. Zbl 1158.68550Efrat, Alon; Fekete, Sándor P.; Gaddehosur, Poornananda R.; Mitchell, Joseph S. B.; Polishchuk, Valentin; Suomela, Jukka 5 2008 On the complexity of minimum-link path problems. Zbl 1362.65027Kostitsyna, Irina; Löffler, Maarten; Polishchuk, Valentin; Staals, Frank 4 2017 Maximum thick paths in static and dynamic environments. Zbl 1192.65022Arkin, Esther M.; Mitchell, Joseph S. B.; Polishchuk, Valentin 3 2010 Analysing local algorithms in location-aware quasi-unit-disk graphs. Zbl 1228.05273Hassinen, Marja; Kaasinen, Joel; Kranakis, Evangelos; Polishchuk, Valentin; Suomela, Jukka; Wiese, Andreas 3 2011 Shortest path to a segment and quickest visibility queries. Zbl 1405.68392Arkin, Esther M.; Efrat, Alon; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Rote, Günter; Schlipf, Lena; Talvitie, Topi 3 2016 Geometric \(k\) shortest paths. Zbl 1371.68292Eriksson-Bique, Sylvester; Hershberger, John; Polishchuk, Valentin; Speckmann, Bettina; Suri, Subhash; Talvitie, Topi; Verbeek, Kevin; Yıldız, Hakan 3 2015 On minimizing crossings in storyline visualizations. Zbl 1471.68200Kostitsyna, Irina; Nöllenburg, Martin; Polishchuk, Valentin; Schulz, André; Strash, Darren 3 2015 An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains. Zbl 1410.68374Mitchell, Joseph S. B.; Polishchuk, Valentin; Sysikaski, Mikko; Wang, Haitao 3 2019 The snowblower problem. Zbl 1188.93052Arkin, Esther M.; Bender, Michael A.; Mitchell, Joseph S. B.; Polishchuk, Valentin 2 2008 Convex transversals. Zbl 1342.68325Arkin, Esther M.; Dieckmann, Claudia; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Schlipf, Lena; Yang, Shang 2 2011 Two new classes of Hamiltonian graphs. (Extended abstract). Zbl 1341.05140Arkin, Esther M.; Mitchell, Joseph S. B.; Polishchuk, Valentin 2 2007 Order-\(k\) \(\alpha\)-hulls and \(\alpha\)-shapes. Zbl 1329.68265Krasnoshchekov, Dmitry; Polishchuk, Valentin 2 2014 The minimum backlog problem. Zbl 1330.68350Bender, Michael A.; Fekete, Sándor P.; Kröller, Alexander; Liberatore, Vincenzo; Mitchell, Joseph S. B.; Polishchuk, Valentin; Suomela, Jukka 2 2015 Routing multi-class traffic flows in the plane. Zbl 1239.90026Kim, Joondong; Mitchell, Joseph S. B.; Polishchuk, Valentin; Yang, Shang; Zou, Jingyu 1 2012 Shape approximation using \(k\)-order alpha-hulls. Zbl 1284.68609Krasnoshchekov, Dmitry N.; Polishchuk, Valentin; Vihavainen, Arto 1 2010 Faster algorithms for minimum-link paths with restricted orientations. Zbl 1342.68340Polishchuk, Valentin; Sysikaski, Mikko 1 2011 Simple wriggling is hard unless you are a fat hippo. Zbl 1253.68155Kostitsyna, Irina; Polishchuk, Valentin 1 2012 An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains. Zbl 1440.68314Mitchell, Joseph S. B.; Polishchuk, Valentin; Sysikaski, Mikko; Wang, Haitao 1 2015 Scandinavian thins on top of cake: new and improved algorithms for stacking and packing. Zbl 1303.68143Alt, Helmut; Arkin, Esther M.; Efrat, Alon; Hart, George; Hurtado, Ferran; Kostitsyna, Irina; Kröller, Alexander; Mitchell, Joseph S. B.; Polishchuk, Valentin 1 2014 Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty. Zbl 1314.90069Golovin, Daniel; Goyal, Vineet; Polishchuk, Valentin; Ravi, R.; Sysikaski, Mikko 1 2015 Shortest path to a segment and quickest visibility queries. Zbl 1378.68150Arkin, Esther M.; Efrat, Alon; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Rote, Günter; Schlipf, Lena; Talvitie, Topi 1 2015 Computing the \(L_1\) geodesic diameter and center of a polygonal domain. Zbl 1388.68280Bae, Sang Won; Korman, Matias; Mitchell, Joseph S. B.; Okamoto, Yoshio; Polishchuk, Valentin; Wang, Haitao 1 2016 On the complexity of minimum-link path problems. Zbl 1387.68265Kostitsyna, Irina; Löffler, Maarten; Polishchuk, Valentin; Staals, Frank 1 2016 Computing the \(L_1\) geodesic diameter and center of a polygonal domain. Zbl 1370.68293Bae, Sang Won; Korman, Matias; Mitchell, Joseph S. B.; Okamoto, Yoshio; Polishchuk, Valentin; Wang, Haitao 1 2017 Recognizing a DOG is hard, but not when it is thin and unit. Zbl 1369.68269Evans, William; Van Garderen, Mereke; Löffler, Maarten; Polishchuk, Valentin 1 2016 Altitude terrain guarding and guarding uni-monotone polygons. Zbl 1427.52004Daescu, Ovidiu; Friedrichs, Stephan; Malik, Hemant; Polishchuk, Valentin; Schmidt, Christiane 1 2019 An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains. Zbl 1410.68374Mitchell, Joseph S. B.; Polishchuk, Valentin; Sysikaski, Mikko; Wang, Haitao 3 2019 Altitude terrain guarding and guarding uni-monotone polygons. Zbl 1427.52004Daescu, Ovidiu; Friedrichs, Stephan; Malik, Hemant; Polishchuk, Valentin; Schmidt, Christiane 1 2019 On the complexity of minimum-link path problems. Zbl 1362.65027Kostitsyna, Irina; Löffler, Maarten; Polishchuk, Valentin; Staals, Frank 4 2017 Computing the \(L_1\) geodesic diameter and center of a polygonal domain. Zbl 1370.68293Bae, Sang Won; Korman, Matias; Mitchell, Joseph S. B.; Okamoto, Yoshio; Polishchuk, Valentin; Wang, Haitao 1 2017 Shortest path to a segment and quickest visibility queries. Zbl 1405.68392Arkin, Esther M.; Efrat, Alon; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Rote, Günter; Schlipf, Lena; Talvitie, Topi 3 2016 Computing the \(L_1\) geodesic diameter and center of a polygonal domain. Zbl 1388.68280Bae, Sang Won; Korman, Matias; Mitchell, Joseph S. B.; Okamoto, Yoshio; Polishchuk, Valentin; Wang, Haitao 1 2016 On the complexity of minimum-link path problems. Zbl 1387.68265Kostitsyna, Irina; Löffler, Maarten; Polishchuk, Valentin; Staals, Frank 1 2016 Recognizing a DOG is hard, but not when it is thin and unit. Zbl 1369.68269Evans, William; Van Garderen, Mereke; Löffler, Maarten; Polishchuk, Valentin 1 2016 Geometric \(k\) shortest paths. Zbl 1371.68292Eriksson-Bique, Sylvester; Hershberger, John; Polishchuk, Valentin; Speckmann, Bettina; Suri, Subhash; Talvitie, Topi; Verbeek, Kevin; Yıldız, Hakan 3 2015 On minimizing crossings in storyline visualizations. Zbl 1471.68200Kostitsyna, Irina; Nöllenburg, Martin; Polishchuk, Valentin; Schulz, André; Strash, Darren 3 2015 The minimum backlog problem. Zbl 1330.68350Bender, Michael A.; Fekete, Sándor P.; Kröller, Alexander; Liberatore, Vincenzo; Mitchell, Joseph S. B.; Polishchuk, Valentin; Suomela, Jukka 2 2015 An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains. Zbl 1440.68314Mitchell, Joseph S. B.; Polishchuk, Valentin; Sysikaski, Mikko; Wang, Haitao 1 2015 Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty. Zbl 1314.90069Golovin, Daniel; Goyal, Vineet; Polishchuk, Valentin; Ravi, R.; Sysikaski, Mikko 1 2015 Shortest path to a segment and quickest visibility queries. Zbl 1378.68150Arkin, Esther M.; Efrat, Alon; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Rote, Günter; Schlipf, Lena; Talvitie, Topi 1 2015 Minimum-link paths revisited. Zbl 1290.65016Mitchell, Joseph S. B.; Polishchuk, Valentin; Sysikaski, Mikko 7 2014 Convex transversals. Zbl 1281.65027Arkin, Esther M.; Dieckmann, Claudia; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Schlipf, Lena; Yang, Shang 5 2014 Order-\(k\) \(\alpha\)-hulls and \(\alpha\)-shapes. Zbl 1329.68265Krasnoshchekov, Dmitry; Polishchuk, Valentin 2 2014 Scandinavian thins on top of cake: new and improved algorithms for stacking and packing. Zbl 1303.68143Alt, Helmut; Arkin, Esther M.; Efrat, Alon; Hart, George; Hurtado, Ferran; Kostitsyna, Irina; Kröller, Alexander; Mitchell, Joseph S. B.; Polishchuk, Valentin 1 2014 Routing multi-class traffic flows in the plane. Zbl 1239.90026Kim, Joondong; Mitchell, Joseph S. B.; Polishchuk, Valentin; Yang, Shang; Zou, Jingyu 1 2012 Simple wriggling is hard unless you are a fat hippo. Zbl 1253.68155Kostitsyna, Irina; Polishchuk, Valentin 1 2012 Analysing local algorithms in location-aware quasi-unit-disk graphs. Zbl 1228.05273Hassinen, Marja; Kaasinen, Joel; Kranakis, Evangelos; Polishchuk, Valentin; Suomela, Jukka; Wiese, Andreas 3 2011 Convex transversals. Zbl 1342.68325Arkin, Esther M.; Dieckmann, Claudia; Knauer, Christian; Mitchell, Joseph S. B.; Polishchuk, Valentin; Schlipf, Lena; Yang, Shang 2 2011 Faster algorithms for minimum-link paths with restricted orientations. Zbl 1342.68340Polishchuk, Valentin; Sysikaski, Mikko 1 2011 Almost stable matchings by truncating the Gale-Shapley algorithm. Zbl 1204.68144Floréen, Patrik; Kaski, Petteri; Polishchuk, Valentin; Suomela, Jukka 5 2010 Maximum thick paths in static and dynamic environments. Zbl 1192.65022Arkin, Esther M.; Mitchell, Joseph S. B.; Polishchuk, Valentin 3 2010 Shape approximation using \(k\)-order alpha-hulls. Zbl 1284.68609Krasnoshchekov, Dmitry N.; Polishchuk, Valentin; Vihavainen, Arto 1 2010 Geometric stable roommates. Zbl 1191.68753Arkin, Esther M.; Bae, Sang Won; Efrat, Alon; Okamoto, Kazuya; Mitchell, Joseph S. B.; Polishchuk, Valentin 10 2009 Not being (super)thin or solid is hard: A study of grid Hamiltonicity. Zbl 1193.05105Arkin, Esther M.; Fekete, Sándor P.; Islam, Kamrul; Meijer, Henk; Mitchell, Joseph S. B.; Núñez-Rodríguez, Yurai; Polishchuk, Valentin; Rappaport, David; Xiao, Henry 9 2009 A simple local 3-approximation algorithm for vertex cover. Zbl 1214.68468Polishchuk, Valentin; Suomela, Jukka 6 2009 A local 2-approximation algorithm for the vertex cover problem. Zbl 1261.68161Åstrand, Matti; Floréen, Patrik; Polishchuk, Valentin; Rybicki, Joel; Suomela, Jukka; Uitto, Jara 6 2009 Minimum-perimeter enclosures. Zbl 1186.68509Mitchell, Joseph S. B.; Polishchuk, Valentin 6 2008 Improved approximation algorithms for relay placement. Zbl 1158.68550Efrat, Alon; Fekete, Sándor P.; Gaddehosur, Poornananda R.; Mitchell, Joseph S. B.; Polishchuk, Valentin; Suomela, Jukka 5 2008 The snowblower problem. Zbl 1188.93052Arkin, Esther M.; Bender, Michael A.; Mitchell, Joseph S. B.; Polishchuk, Valentin 2 2008 Thick non-crossing paths and minimum-cost flows in polygonal domains. Zbl 1221.68277Polishchuk, Valentin; Mitchell, Joseph S. B. 6 2007 Two new classes of Hamiltonian graphs. (Extended abstract). Zbl 1341.05140Arkin, Esther M.; Mitchell, Joseph S. B.; Polishchuk, Valentin 2 2007 all cited Publications top 5 cited Publications all top 5 Cited by 247 Authors 11 Polishchuk, Valentin 8 Mitchell, Joseph S. B. 6 Suomela, Jukka 5 Korman, Matias 4 Fekete, Sándor P. 4 Manlove, David F. 4 Wang, Haitao 3 Ahn, Hee-Kap 3 Aichholzer, Oswin 3 Arkin, Esther M. 3 Bose, Prosenjit K. 3 Díaz-Báñez, Jose Miguel 3 Fabila-Monroy, Ruy 3 Kostitsyna, Irina 3 Seara, Carlos 3 Suri, Subhash 3 Sysikaski, Mikko 2 Barba, Luis Felipe 2 Caraballo, Luis-Evaristo 2 Claverol, Mercè 2 Collette, Sébastien 2 de Carufel, Jean-Lou 2 Edelsbrunner, Herbert 2 Floréen, Patrik 2 Göös, Mika 2 Hackl, Thomas 2 Hassinen, Marja 2 Hershberger, John E. 2 Hoefer, Martin 2 Kaasinen, Joel 2 Kaski, Petteri 2 Katz, Matthew J. 2 Kröller, Alexander 2 Kumar, Neeraj 2 Langerman, Stefan 2 Löffler, Maarten 2 Möller, Daniel 2 Oh, Eunjin 2 Osang, Georg 2 Paturi, Ramamohan 2 Pilz, Alexander 2 Schneider, Stefan 2 Silveira, Rodrigo I. 2 Vogtenhuber, Birgit 2 Żyliński, Paweł 1 Akhoondian Amiri, Saeed 1 Aloupis, Greg 1 Alt, Helmut 1 Anshelevich, Elliot 1 Aras, Necati 1 Arseneva, Elena 1 Aschner, Rom 1 Ausserhofer, Markus 1 Bhardwaj, Onkar 1 Biedl, Therese C. 1 Biniaz, Ahmad 1 Biró, Peter 1 Biswas, Arindam 1 Brandt, Felix 1 Burkett, Justin 1 Calinescu, Gruia 1 Carmi, Paz 1 Chaitman-Yerushalmi, Lilach 1 Chambers, Erin Wolf 1 Charkari, Nasrollah Moghaddam 1 Chiu, Man-Kwun 1 Damian, Mirela 1 Dann, Susanna 1 De Biasi, Marzio 1 Degener, Bastian 1 Deĭneko, Vladimir G. 1 Delorme, Maxence 1 Demaine, Erik D. 1 D’Emidio, Mattia 1 Di Giacomo, Emilio 1 Di Stefano, Gabriele 1 Didimo, Walter 1 Dumitrescu, Adrian 1 Durocher, Stephane 1 Efrat, Alon 1 Emek, Yuval 1 Erdem, Esra 1 Erickson, Alejandro 1 Erickson, Jeff 1 Fidan, Müge 1 Fink, Martin 1 Fischer, Anja 1 Fischer, Norbert 1 Flanagan, Francis X. 1 Flatland, Robin Y. 1 Flores-Peñaloza, David 1 Förster, Klaus-Tycho 1 Fujito, Toshihiro 1 García, Sergio 1 Garijo, Delia 1 Gąsieniec, Leszek Antoni 1 Gondzio, Jacek 1 Griffith, Amanda L. 1 Grimmer, Benjamin 1 Gronemann, Martin ...and 147 more Authors all top 5 Cited in 25 Serials 16 Computational Geometry 11 Algorithmica 5 Discrete Applied Mathematics 5 Theoretical Computer Science 5 Discrete & Computational Geometry 3 European Journal of Operational Research 3 Distributed Computing 3 Theory of Computing Systems 3 Journal of Combinatorial Optimization 2 Journal of Geometry 2 International Journal of Computational Geometry & Applications 1 Information Processing Letters 1 Applied Mathematics and Computation 1 Operations Research 1 SIAM Journal on Computing 1 Social Choice and Welfare 1 Graphs and Combinatorics 1 SIAM Journal on Discrete Mathematics 1 Constraints 1 Fundamenta Informaticae 1 Trudy Instituta Matematiki 1 Theory and Practice of Logic Programming 1 Optimization Letters 1 Algorithms 1 Computer Science Review all top 5 Cited in 12 Fields 62 Computer science (68-XX) 20 Combinatorics (05-XX) 20 Operations research, mathematical programming (90-XX) 12 Convex and discrete geometry (52-XX) 11 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 6 Numerical analysis (65-XX) 3 Geometry (51-XX) 1 General and overarching topics; collections (00-XX) 1 Mathematical logic and foundations (03-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) 1 Statistics (62-XX) Citations by Year