Papers from GWOP
The following publications were started at or influenced by work done at our Gremo Workshops on Open Problems.
-
"Call Admission in Star Networks"
Udo Adamy, Thomas Erlebach, Dieter Mitsche, Ingo Schurr, Bettina Speckmann, and Emo Welzl.
Proc. 2nd Internat. Workshop Approximation and Online Algorithms (WAOA 2004), Lecture Notes Comput. Sci., Volume 3351, Bergen, Norway, 2005, 211-224.
-
"Algorithms for center and Tverberg points"
Pankaj K. Agarwal, Micha Sharir, and Emo Welzl.
Proc. 20th Internat. Sympos. Comput. Geom. (SoCG 2004), Brooklyn, New York, USA, 2004, 61-67.
-
"Algorithms for center and Tverberg points"
Pankaj K. Agarwal, Micha Sharir, and Emo Welzl.
ACM Trans. Algorithms, Volume 5(1), 2008, 5:1-5:20.
-
"Coloring Octrees"
Udo Adamy, Michael Hoffmann, József Solymosi, and Miloš Stojaković.
Proc. 10th Ann. Internat. Conf. Computing and Combinatorics (COCOON 2004), Lecture Notes Comput. Sci., Volume 3106, Jeju Island, Korea, 2004, 62-71.
-
"Coloring Octrees"
Udo Adamy, Michael Hoffmann, József Solymosi, and Miloš Stojaković.
Theoret. Comput. Sci., Volume 363(1), 2006, 11-17.
-
"An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks"
Christoph Ambühl.
Proc. 32nd Internat. Colloq. Automata Lang. Prog. (ICALP 2005), Lecture Notes Comput. Sci., Volume 3580, Lisbon, Portugal, 2005, 1139-1150.
-
"Core Stability of Minimum Coloring Games"
Thomas Bietenhader and Yoshio Okamoto.
Math. Oper. Res., Volume 31(2), 2006, 418-431.
-
"Unique Sink Orientation on Ladders"
Leonard Y. Rüst.
Chapter 3.3 in The P-Matrix Linear Complementarity Problem-Generalizations and Specializations, Diss. ETH, Volume 17387, 2007, 36-57.
-
"Relaxed Two-coloring of Cubic Graphs"
Robert Berke and Tibor Szabó.
J. Combin. Theory Ser. B, Volume 97(4), 2007, 652-668.
-
"Approximate Sorting"
Joachim Giesen, Eva Schuberth, and Miloš Stojaković.
Proc. 7th Latin Amer. Sympos. Theoret. Informatics (LATIN 2006), Lecture Notes Comput. Sci., Volume 3887, Valdivia, Chile, 2006, 524-531.
-
"Approximate Sorting"
Joachim Giesen, Eva Schuberth, and Miloš Stojaković.
Fundam. Inform., Volume 90(1-2), 2009, 67-72.
-
"On Rolling Cube Puzzles"
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El Khechen, Sándor P. Fekete, Christian Knauer, André Schulz, and Perouz Taslakian.
Proc. 19th Canad. Conf. Comput. Geom. (CCCG 2007), Ottawa (ON), Canada, 2007, 141-144.
-
"Transforming spanning trees: A lower bound"
Kevin Buchin, Andreas Razen, Takeaki Uno, and Uli Wagner.
Abstracts 23rd European Workshop Comput. Geom. (EuroCG 2007), Graz, Austria, 2007, 166-169.
-
"Transforming spanning trees: A lower bound"
Kevin Buchin, Andreas Razen, Takeaki Uno, and Uli Wagner.
Comput. Geom. Theory Appl., Volume 42(8), 2009, 724-730.
-
"Decomposing Kn with Crossing-Free Partitions"
Andreas Razen.
Chapter 2 in Crossing-Free Configurations on Planar Point Sets, Diss. ETH, Volume 18607, 2009, 47-56.
-
"Polychromatic Colorings of Plane Graphs"
Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, Bettina Speckmann, and Philipp Zumstein.
Proc. 24th Internat. Sympos. Comput. Geom. (SoCG 2008), College Park, MD, USA, 2008, 338-345.
-
"Polychromatic Colorings of Plane Graphs"
Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, Bettina Speckmann, and Philipp Zumstein.
Discrete Comput. Geom., Volume 42(3), 2009, 421-–442.
-
"How Many Conflicts Does It Need to Be Unsatisfiable?"
Dominik Scheder and Philipp Zumstein.
Proc. 11th Internat. Conf. Theory Appl. Satisfiability Testing (SAT 2008), Lecture Notes Comput. Sci., Volume 4996, 2008, 246-256.
-
"Improved Bounds for Wireless Localization"
Tobias Christ, Michael Hoffmann, Yoshio Okamoto, and Takeaki Uno.
Proc. 11th Scand. Workshop Algorithm Theory (SWAT 2008), Lecture Notes Comput. Sci., Volume 5124, Göteborg, Sweden, 2008, 77-89.
-
"Improved Bounds for Wireless Localization"
Tobias Christ, Michael Hoffmann, Yoshio Okamoto, and Takeaki Uno.
Algorithmica, Volume 57(3), 2010, 499-516.
-
"How Long Can a Graph be Kept Planar?"
V. Anuradha, Chinmay Jain, Jack Snoeyink, and Tibor Szabó.
Electr. J. Combin., Volume 15, 2008, #N14.
-
"On Center Regions and Balls Containing Many Points"
Shakhar Smorodinsky, Marek Sulovský, and Uli Wagner.
Proc. 14th Ann. Internat. Conf. Computing and Combinatorics (COCOON 2008), Lecture Notes Comput. Sci., Volume 5092, Dalian, China, 2008, 363-373.
-
"LC Reductions Yield Isomorphic Simplicial Complexes"
Jiří Matoušek.
Contributions Dicrete Math., Volume 3(2), 2008, 37-39.
-
"Maximum and Minimum against k lies"
Michael Hoffmann, Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
Proc. 12th Scand. Sympos. Workshops Algorithm Theory (SWAT 2010), Lecture Notes Comput. Sci., Volume 6139, Bergen, Norway, 2010, 139-149.
-
"Maximum and Minimum against k lies"
Michael Hoffmann, Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
Chicago J. Theoret. Comput. Sci., Volume 2012, 2012, #2.
-
"The t-Pebbling Number is Eventually Linear in t"
Michael Hoffmann, Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
Electr. J. Combin., Volume 18(1), 2011, #P153.
-
"Coloring Geometric Hypergraphs Defined by an Arrangement of Half-planes"
Radoslav Fulek.
Proc. 22nd Canad. Conf. Comput. Geom. (CCCG 2010), Winnipeg (MB), Canada, 2010, 71-74.
-
"A Tight Lower Bound for Convexly Independent Subsets of the Minkowski Sums of Planar Point Sets"
Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin ichi Tanigawa, and Csaba D. Tóth.
Proc. Japan Conf. Discrete Comput. Geom. (JCCGG 2009), Kanazawa, Ishikawa, Japan, 2009.
-
"A Tight Lower Bound for Convexly Independent Subsets of the Minkowski Sums of Planar Point Sets"
Ondřej Bílka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin ichi Tanigawa, and Csaba D. Tóth.
Electr. J. Combin., Volume 17, 2010, #N35.
-
"Consistent Digital Line Segments"
Tobias Christ, Dömötör Pálvölgyi, and Miloš Stojaković.
Proc. 26th Internat. Sympos. Comput. Geom. (SoCG 2010), Snowbird, Utah, USA, 2010, 11-18.
-
"Consistent Digital Line Segments"
Tobias Christ, Dömötör Pálvölgyi, and Miloš Stojaković.
Discrete Comput. Geom., Volume 47(5), 2012, 691-710.
-
"Vectors in a Box"
Kevin Buchin, Jiří Matoušek, Robin A. Moser, and Dömötör Pálvölgyi.
Math. Program., Volume 135(1-2), 2012, 323-335.
-
"Many Collinear k-Tuples with no k+1 Collinear Points"
József Solymosi and Miloš Stojaković.
Discrete Comput. Geom., Volume 50(3), 2013, 811-820.
-
"A Doubly Exponentially Crumbled Cake"
Tobias Christ, Andrea Francke, Heidi Gebauer, Jiří Matoušek, and Takeaki Uno.
Electr. Notes Discrete Math., Volume 38, 2011, 265-271.
-
"An Improved Bound for Orthogeodesic Point Set Embeddings of Trees"
Imre Bárány, Kevin Buchin, Michael Hoffmann, and Anita Liebenau.
Abstracts 32nd European Workshop Comput. Geom. (EuroCG 2016), Lugano, Switzerland, 2016, 47-50.
-
"Free Edge Lengths in Plane Graphs"
Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Morić, Yoshio Okamoto, Tibor Szabó, and Csaba D. Tóth.
Proc. 30th Internat. Sympos. Comput. Geom. (SoCG 2014), Kyoto, Japan, 2014, 426-435.
-
"Free Edge Lengths in Plane Graphs"
Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Morić, Yoshio Okamoto, Tibor Szabó, and Csaba D. Tóth.
Discrete Comput. Geom., Volume 54(1), 2015, 259-289.
-
"A Census of Plane Graphs with Polyline Edges"
Andrea Francke and Csaba D. Tóth.
Proc. 30th Internat. Sympos. Comput. Geom. (SoCG 2014), Kyoto, Japan, 2014, 242-250.
-
"A Census of Plane Graphs with Polyline Edges"
Andrea Francke and Csaba D. Tóth.
SIAM J. Discrete Math., Volume 31(2), 2017, 1174-1195.
-
"Towards the Hanani-Tutte Theorem for Clustered Graphs"
Radoslav Fulek.
Proc. 40th Internat. Workshop Graph-Theoret. Concepts Comput. Sci. (WG 2014), Lecture Notes Comput. Sci., Volume 8747, 2014, 176-188.
-
"Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips)"
Uli Wagner and Emo Welzl.
Proc. 31st ACM-SIAM Sympos. Discrete Algorithms (SODA '20), Salt Lake City (UT), USA, 2020, 2823-2841.
-
"Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)"
Uli Wagner and Emo Welzl.
Proc. 36th Internat. Sympos. Comput. Geom. (SoCG 2020), Zürich, Switzerland, 2020, 67:1-67:16.
-
"Connectivity of Triangulation Flip Graphs in the Plane"
Uli Wagner and Emo Welzl.
Discrete Comput. Geom., Volume 68(4), 2022, 1227-–1284.
-
"Arc diagrams, flip distances, and Hamiltonian triangulations"
Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein.
Proc. 32nd Sympos. Theoret. Aspects Comput. Sci. (STACS 2015), LIPIcs, Volume 30, München, Germany, 2015, 197-210.
-
"Arc diagrams, flip distances, and Hamiltonian triangulations"
Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein.
Comput. Geom. Theory Appl., Volume 68, 2018, 206-225.
-
"Approximation and Hardness of Token Swapping"
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno.
Proc. 24th European Sympos. Algorithms (ESA 2016), LIPIcs, Volume 57, München, Germany, 2016, 66:1-66:15.
-
"On the Existence of Ordinary Triangles"
Radoslav Fulek, Hossein Nassajian Mojarrad, Márton Naszódi, József Solymosi, Sebastian U. Stich, and May Szedlák.
Comput. Geom. Theory Appl., Volume 66, 2017, 28-31.
-
"Deterministic Algorithms for Unique Sink Orientations of Grids"
Luis Barba, Malte Milatz, Jerri Nummenpalo, and Antonis Thomas.
Proc. 22nd Ann. Internat. Conf. Computing and Combinatorics (COCOON 2016), Lecture Notes Comput. Sci., Volume 9797, Ho Chi Minh City, Vietnam, 2016, 357-369.
-
"The Complexity of Optimization on Grids"
Luis Barba, Malte Milatz, Jerri Nummenpalo, Xiaoming Sun, Antonis Thomas, Jialin Zhang, and Zhijie Zhang.
Algorithmica, Volume 81(9), 2019, 3494-3518.
-
"Crossing-Free Perfect Matchings in Wheel Point Sets"
Andres J. Ruiz Vargas and Emo Welzl.
A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, 2017.
-
"Green-Wins Solitaire Revisited-Simultaneous Flips that Affect Many Edges"
Michael Hoffmann, János Pach, and Miloš Stojaković.
Abstracts 35th European Workshop Comput. Geom. (EuroCG 2019), Utrecht, Netherlands, 2019, 9:1-9:6.
-
"Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems"
Jean Cardinal, Jerri Nummenpalo, and Emo Welzl.
Proc. 12th Internat. Sympos. on Parameterized and Exact Computation (IPEC 2017), LIPIcs, Volume 89, Vienna, Austria, 2017, 11:1-11:12.
-
"Solving and Sampling with Many Solutions"
Jean Cardinal, Jerri Nummenpalo, and Emo Welzl.
Algorithmica, Volume 82(5), 2020, 1474-1489.
-
"Lower Bounds for Searching Robots, some Faulty"
Andrey Kupavskii and Emo Welzl.
Proc. 37th ACM Sympos. Principles Distrib. Comput. (PODC 2018), Egham, United Kingdom, 2018, 447-453.
-
"Lower Bounds for Searching Robots, some Faulty"
Andrey Kupavskii and Emo Welzl.
Distributed Comput., Volume 34(4), 2021, 229-237.
-
"Transition Operations over Plane Trees"
Torrie L. Nichols, Alexander Pilz, Csaba D. Tóth, and Ahad N. Zehmakan.
Proc. 13th Latin Amer. Sympos. Theoret. Informatics (LATIN 2018), Lecture Notes Comput. Sci., Volume 10807, Buenos Aires, Argentina, 2018, 835-848.
-
"Transition Operations over Plane Trees"
Torrie L. Nichols, Alexander Pilz, Csaba D. Tóth, and Ahad N. Zehmakan.
Discrete Math., Volume 343(8), 2020, 111929.
-
"An Improved Searching Algorithm on a Line by Four Truthful Robots and Two Byzantine Robots"
Michael Hoffmann, Malte Milatz, Yoshio Okamoto, and Manuel Wettstein.
Abstracts 22nd Japan Conf. Discrete Comput. Geom. Graphs (JCDCG3 '19), Tokyo, Japan, 2019, 69-70.
-
"Simple Topological Drawings of k-Planar Graphs"
Chih Hung Liu, Meghana M. Reddy, and Csaba D. Tóth.
Abstracts 36th European Workshop Comput. Geom. (EuroCG '20), Würzburg, Germany, 2020, 80:1-80:6.
-
"Simple Topological Drawings of k-Planar Graphs"
Michael Hoffmann, Chih Hung Liu, Meghana M. Reddy, and Csaba D. Tóth.
Proc. 28th Internat. Sympos. Graph Drawing (GD '20), Lecture Notes Comput. Sci., Volume 12590, Vancouver, Canada, 2020, 390-402.
-
"Efficient Generation of Rectangulations via Permutation Languages"
Arturo Merino and Torsten Mütze.
Proc. 37th Internat. Sympos. Comput. Geom. (SoCG 2021), Buffalo (NY), USA, 2021, 54:1-54:18.
-
"On the VC-dimension of Half-Spaces with respect to Convex Sets"
Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, and Shakhar Smorodinsky.
Discrete Math. Theoret. Comput. Sci., Volume 23(3), 2021, #2.
-
"On the Multi-Robber Damage Number"
Miloš Stojaković and Lasse Wulf.
CoRR, Volume abs/2209.10965, 2022.
-
"Optimizing Symbol Visibility through Displacement"
Bernd Gärtner, Vishwas Kalani, Wouter Meulemans, Meghana M. Reddy, Bettina Speckmann, and Miloš Stojaković.
CoRR, Volume abs/2310.01147, 2023.
-
"A Note on the Faces of the Dual Koch Arrangement"
Bernd Gärtner and Manuel Wettstein.
CoRR, Volume abs/2302.14125, 2023.
-
"Recognition of Unit Segment and Polyline Graphs is ER-Complete"
Michael Hoffmann, Tillmann Miltzow, Simon Weber, and Lasse Wulf.
Abstracts 40th European Workshop Comput. Geom. (EuroCG '24), Ioannina, Greece, 2024, 11:1-11:10.
-
"Recognition of Unit Segment and Polyline Graphs is ER-Complete"
Michael Hoffmann, Tillmann Miltzow, Simon Weber, and Lasse Wulf.
50th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '24), Lecture Notes Comput. Sci., Volume ??, Gozd Martuljek, Slovenia, 2024, ??-??.
Last modified: Thu Jun 13 14:19:35 CEST 2019
Valid HTML5