The Algorithms Research Group is part of the Computer Science Department, inside the Faculty of Sciences of ULB.
News
News and seminar announcements are posted here.
Topics
The Algorithms Research Group centers its activities on graph algorithms,
computational geometry, data structures, optimization
algorithms, data compression, and information theory.
Permanent Staff
|
Jean Cardinal
Associate Professor
Keywords: Information theory, graphs, algorithms.
Address: N8.110, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5608
Fax: 02/650.5609
E-mail: jcardin@ulb.ac.be
|
|
| | | | | | | |
|
|
Samuel Fiorini
Associate Professor (Math Department)
Keywords: Combinatorial optimization, Polyhedral combinatorics, Graph Theory.
E-mail: sfiorini@ulb.ac.be
|
|
| | | | | | | |
|
|
Stefan Langerman
Maître de recherches (FNRS Senior Research Associate)
Keywords: Computational geometry, data structures.
Address: O8.113, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5928
Fax: 02/650.5609
E-mail: Stefan.Langerman@ulb.ac.be
|
|
Post-Docs
|
|
Greg Aloupis
Chargé de recherches du FNRS (FNRS Postdoctoral Researcher)
Keywords: Computational geometry.
Address: O8.214, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5612
Fax: 02/650.5609
E-mail: aloupis.greg@gmail.com
|
|
| | | | | | | |
|
|
Gwenaël Joret
Chargé de recherches du FNRS (FNRS Postdoctoral Researcher)
Keywords: Graph theory.
Address: O8.101, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5875
Fax: 02/650.5609
E-mail: gjoret@ulb.ac.be
|
|
| | | | | | | |
|
|
Marcin Kamiński
Chargé de recherches du FNRS (FNRS Postdoctoral Researcher)
Keywords: Graph theory, Algorithms.
Address: O8.114, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5960
Fax: 02/650.5609
E-mail: Marcin.Kaminski@ulb.ac.be
|
|
| | | | | | | |
|
|
Matias Korman
Postdoctoral Researcher
Keywords: Computational geometry.
Address: O8.114, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5960
Fax: 02/650.5609
E-mail: mkormanc@ulb.ac.be
|
|
| | | | | | | |
|
|
Perouz Taslakian
Postdoctoral Researcher
Keywords: Computational Geometry, Computational Music Theory
Address: O8.214, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5612
Fax: 02/650.5609
E-mail: Perouz.Taslakian@ulb.ac.be
|
|
Ph.D. Students
|
|
Frédéric Pluquet
Teaching Assistant
Keywords: Persistent data structures, Decomposition and Composition of programs.
Address: N8.217, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5601
Fax: 02/650.5609
E-mail: fpluquet@ulb.ac.be
|
|
| | | | | | | |
|
|
Christophe Dumeunier
PhD Student
Keywords: Computational geometry, graph theory.
Address: O8.114, CP 212, Bvd. du Triomphe, 1050 Bruxelles
Tel: 02/650.5960
Fax: 02/650.5609
E-mail: cdumeuni@ulb.ac.be
|
|
External Members
Visitors in 2011
|
|
Dimitrios Thilikos - University of Athens
|
| |
Ian Munro - University of Waterloo
|
|
|
Tetsuo Asano - JAIST
|
|
|
Ozgur Ozkan - Polytechnic Institute of NYU
|
|
|
Stefanie Wuhrer - Saarland University
|
|
|
Sergio Cabello - University of Ljubljana
|
|
|
David Wood - Monash University
|
|
|
Luis Felipe Barba - UNAM
|
|
|
Naomi Nishimura - University of Waterloo
|
|
|
Shakhar Smorodinsky - Ben-Gurion University
|
|
|
Ferran Hurtado - Universitat Politecnica de Catalunya
|
|
|
Nicolas Trotignon - Ecole Normale Superieure de Lyon
|
|
|
Hiro Ito - Kyoto University
|
|
|
John Iacono - Polytechnic Institute of NYU
|
|
|
Daniel Paulusma - Durham University
|
|
|
Martin Milanic - University of Primorska
|
Recent Journal Publications
|
[1]
|
V. Dujmovic and S. Langerman.
A center transversal theorem for hyperplanes and applications to
graph drawing.
In Proceedings of the 2011 ACM Symposium on Computational
Geometry (SoCG 2011), to appear.
|
|
[2]
|
Y. Higashikawa, N. Katoh, S. Langerman, and S. Tanigawa.
Online graph exploration algorithms for cycles and trees by multiple
searchers.
In China-Japan Joint Conference on Computational Geometry,
Graphs and Applications (CGGA 2010), to appear.
|
|
[3]
|
International Symposium on Theoretical Aspects of Computer Science, STACS
2010, Nancy, France, March, 4-6, 2010, Proceedings, to appear.
|
|
[4]
|
J. M. Díaz-Bá nez, P. Pérez-Lantero, M. Korman, and I. Ventura.
Locating a service facility and a rapid transit line.
In Submitted to the XIV Spanish Meeting on Computational
Geometry, 2011.
|
|
[5]
|
J. M. Díaz-Bá nez, P. Pérez-Lantero, M. Korman, and I. Ventura.
The 1-center and 1-highway problem.
In Submitted to the XIV Spanish Meeting on Computational
Geometry, 2011.
|
|
[6]
|
M. Korman.
Yet another paper on minimizing interference on ad-hoc networks.
volume abs/1101.0565, 2011.
[ http ]
|
|
[7]
|
Jean Cardinal and Matias Korman.
Coloring planar homothets and three-dimensional hypergraphs.
In Proc. of the 27th European Workshop on Computational
Geometry, 2011.
[ http ]
|
|
[8]
|
G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine, M. L. Demaine, M. Dulieu,
R. Fabila-Monroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara,
and P. Taslakian.
Matching points with things.
In Proceedings of the 8th Latin American Theoretical Informatics
(LATIN'10), LNCS, 2010.
|
|
[9]
|
G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman,
O. Schwartz, S. Smorodinsky, and P. Taslakian.
Colorful strips.
In Proceedings of the 8th Latin American Theoretical Informatics
(LATIN'10), LNCS, 2010.
|
|
[10]
|
J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers, and J. I. Munro.
Sorting under partial information (without the ellipsoid algorithm).
In Proc. ACM Symposium on Theory of Computing (STOC), pages
359-368. ACM, 2010.
|
|
[11]
|
S.-W. Cheng, C. Knauer, S. Langerman, and M. Smid.
Approximating the average stretch factor of geometric graphs.
In Proceedings of the International Symposium on Algorithms and
Computation (ISAAC 2010), volume 5606 of LNCS, pages 37-48.
Springer-Verlag, 2010.
[ DOI ]
|
|
[12]
|
Y. Higashikawa, N. Katoh, S. Langerman, and S. Tanigawa.
Online graph exploration algorithms for cycles and trees by multiple
searchers.
In Abstracts of the 3rd Annual Meeting of the Asian Association
for Algorithms and Computation (AAAC 2010), 2010.
|
|
[13]
|
Christophe Paul and Michel Habib, editors.
Graph-Theoretic Concepts in Computer Science, 35th International
Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers,
volume 5911 of Lecture Notes in Computer Science, 2010.
|
|
[14]
|
Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Stefan Szeider, and
Dimitrios M. Thilikos.
On contracting graphs to fixed pattern graphs.
In van Leeuwen et al. [15], pages 503-514.
|
|
[15]
|
Jan van Leeuwen, Anca Muscholl, David Peleg, Jaroslav Pokorný, and Bernhard
Rumpe, editors.
SOFSEM 2010: Theory and Practice of Computer Science, 36th
Conference on Current Trends in Theory and Practice of Computer Science,
Spindleruv Mlýn, Czech Republic, January 23-29, 2010. Proceedings,
volume 5901 of Lecture Notes in Computer Science. Springer, 2010.
|
|
[16]
|
J. Fiala, M. Kamiński, B. Lidický, and D. Paulusma.
The k-in-a-path problem for claw-free graphs.
In STACS [3].
|
|
[17]
|
Sang Won Bae, Matias Korman, and Yoshio Okamoto.
The geodesic diameter of polygonal domains.
In Proc. of the 18th European Symposium on Algorithms, LNCS,
pages 500-511, 2010.
[ http ]
|
|
[18]
|
Shinya Anzai, Jinhee Chun, Ryosei Kasai, Matias Korman, and Takeshi Tokuyama.
Effect of corner information in simultaneous placement of k
rectangles and tableaux.
In Proceedings of the 16th international conference on Computing
and Combinatorics (COCOON'10), LNCS, pages 235-243, 2010.
[ .pdf ]
|
|
[19]
|
J. Cardinal and M. Korman.
Coloring planar homothets and three-dimensional hypergraphs.
volume abs/1101.0565, 2010.
[ http ]
|
|
[20]
|
Sang Won Bae, Matias Korman, and Yoshio Okamoto.
The geodesic diameter of polygonal domains.
In Proc. of the 26th European Workshop on Computational
Geometry, pages 49-52, 2010.
[ .pdf ]
|
|
[21]
|
Isabel Hubard and Perouz Taslakian.
Deflating polygons to the limit.
In Proceedings of the 22nd Canadian Conference on Computational
Geometry (CCCG 2010), pages 67-70, August 2010.
|
|
[22]
|
G. Aloupis, J. Cardinal, S. Collette, S. Langerman, D. Orden, and P. Ramos.
Decomposition of multiple coverings into more parts.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
(SODA'09), 2009.
|
|
[23]
|
Greg Aloupis, Nadia Benbernou, Mirela Damian, Erik Demaine, Robin Flatland,
John Iacono, and Stefanie Wuhrer.
Efficient reconfiguration for lattice-based modular robots.
In Proc. European Conference on Mobile Robotics, pages 81-86,
2009.
|
|
[24]
|
J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers, and J. I. Munro.
An efficient algorithm for partial order production.
In Proc. ACM Symposium on Theory of Computing (STOC), pages
93-100. ACM, 2009.
[ http ]
|
|
[25]
|
J. Cardinal, S. Fiorini, and G. Joret.
Minimum entropy combinatorial optimization problems.
In Proc. Computability in Europe (CiE), volume 5635 of
Lecture Notes in Computer Science, pages 79-88. Springer-Verlag, 2009.
[ http ]
|
|
[26]
|
J. Cardinal, E. D. Demaine, M. L. Demaine, S. Imahori, S. Langerman, and
R. Uehara.
Algorithmic folding complexity.
In Proc. International Symposium on Algorithms and Computation
(ISAAC), volume 5878 of Lecture Notes in Computer Science, pages
452-461. Springer-Verlag, 2009.
Also presented at the 7th Japan Conference on Computational Geometry
and Graphs (JCCGG09).
|
|
[27]
|
J. Cardinal, E. D. Demaine, S. Fiorini, G. Joret, I. Newman, and O. Weimann.
The stackelberg minimum spanning tree game on planar and
bounded-treewidth graphs.
In Proc. Workshop on Internet and Network Economics (WINE),
volume 5929 of Lecture Notes in Computer Science, pages 125-136.
Springer-Verlag, 2009.
|
|
[28]
|
Erik D. Demaine, Martin L. Demaine, Stefan Langerman, and Jérôme
Vervier.
Locked thick chains.
In Abstracts from the 25th European Workshop on Computational
Geometry (EuroCG 2009), pages 65-68, Brussels, Belgium, March 2009.
|
|
[29]
|
F. Pluquet, S. Langerman, and R. Wuyts.
Executing code in the past: Efficient in-memory object graph
versioning.
In Proceedings of the 2009 ACM SIGPLAN Conference on
Object-Oriented Programming Systems, Languages, and Applications
(OOPSLA'09), 2009.
|
|
[30]
|
E.D. Demaine, M.L. Demaine, V. Hart, J. Iacono, S. Langerman, and J. O'Rourke.
Continuous blooming of convex polyhedra.
In Abstracts from the 7th Japan Conference on Computational
Geometry and Graphs (JCCGG 2009), pages 123-124, 2009.
|
|
[31]
|
Pim van 't Hof, Marcin Kamiński, and Daniël Paulusma.
Finding induced paths of given parity in claw-free graphs.
In Paul and Habib [13], pages 341-352.
|
|
[32]
|
Takehiro Ito, Marcin Kamiński, and Erik D. Demaine.
Reconfiguration of list edge-colorings in a graph.
In Dehne et al. [33], pages 375-386.
|
|
[33]
|
Frank K. H. A. Dehne, Marina L. Gavrilova, Jörg-Rüdiger Sack, and
Csaba D. Tóth, editors.
Algorithms and Data Structures, 11th International Symposium,
WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings, volume 5664 of
Lecture Notes in Computer Science. Springer, 2009.
|
|
[34]
|
Takehiro Ito, Marcin Kamiński, Daniël Paulusma, and Dimitrios M.
Thilikos.
Parameterizing cut sets in a graph by the number of their components.
In Dong et al. [36], pages 605-615.
|
|
[35]
|
Petr A. Golovach, Marcin Kamiński, Daniël Paulusma, and Dimitrios M.
Thilikos.
Induced packing of odd cycles in a planar graph.
In Dong et al. [36], pages 514-523.
|
|
[36]
|
Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors.
Algorithms and Computation, 20th International Symposium, ISAAC
2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, volume 5878
of Lecture Notes in Computer Science. Springer, 2009.
|
|
[37]
|
Jinhee Chun, Kasai Ryosei, Matias Korman, and Takeshi Tokuyama.
Algorithms for computing the maximum weight region decomposable into
elementary shapes.
In Proceedings of the 20th International Symposium on Algorithms
and Computation (ISAAC'09), LNCS, pages 1166-1174, 2009.
[ DOI |
.pdf ]
|
|
[38]
|
Sang Won Bae, Matias Korman, and Takeshi Tokuyama.
All farthest neighbors in the presence of highways and obstacles.
In Proceedings of the 3rd International Workshop on Algorithms
and Computation (WALCOM'09), LNCS, pages 71-82, 2009.
[ DOI |
.pdf ]
|
|
[39]
|
Hee Kap Ahn, Sang Won Bae, Sang Sub Kim, Matias Korman, Iris Reinbacher, and
Wanbin Son.
Square and rectangle covering with outliers.
In Proceedings of the 3rd Frontiers of Algorithmics Workshop
(FAW'09), LNCS, 2009.
[ DOI |
http ]
|
|
[40]
|
Hee Kap Ahn, Sang Won Bae, Sang Sub Kim, Matias Korman, Iris Reinbacher, and
Wanbin Son.
Square and rectangle covering with outliers.
In Proc. of the 25th European Workshop on Computational
Geometry, 2009.
|
|
[41]
|
Matias Korman and Takeshi Tokuyama.
An improved algorithm for inserting a highway in a city metric based
on quasiconvex optimization techniques.
In Proc. of the 25th European Workshop on Computational
Geometry, 2009.
[ .pdf ]
|
|
[42]
|
M. Korman and T. Tokuyama.
An improved algorithm for inserting a highway in a city metric based
on quasiconvex optimization techniques.
In Proc. of the 2nd Asian Association for Algorithms and
Computation (AAAC'09), 2009.
|
|
[43]
|
Jinhee Chun, Kasai Ryosei, Matias Korman, and Takeshi Tokuyama.
Algorithms for computing the optimal image segmentation of
nonintersecting union of base monotone regions (in japanese).
In Proc. of the 8th Forum on Information Technology (FIT'09),
2009.
[ .pdf ]
|
|
[44]
|
Hee Kap Ahn, Sang Won Bae, Sang Sub Kim, Matias Korman, Iris Reinbacher, and
Wanbin Son.
Square and rectangle covering with outliers.
In Proc. of the Language Automaton Symposium, 2009.
|
|
[45]
|
M. Korman and T. Tokuyama.
An improved algorithm for inserting a highway in a city metric based
on quasiconvex optimization.
In IEICE technical report. Theoretical foundations of Computing
(compKEN), 2009.
|
|
[46]
|
Jinhee Chun, Kasai Ryosei, Matias Korman, and Takeshi Tokuyama.
Algorithms for optimal segmentation of regions decomposable into
basic shapes.
In IEICE technical report. Theoretical foundations of Computing
(compKEN), 2009.
|
|
[47]
|
David Bremner, Erik D. Demaine, Perouz Taslakian, and Godfried T. Toussaint.
Reconstructing points on a circle from labeled distances.
In Proceedings of the 25th European Workshop on Computational
Geometry (EuroCG 2009), pages 155-158, March 2009.
|
|
[48]
|
G. Aloupis, S. Collette, M. Damian, E. Demaine, D. El-Khechen, R. Flatland,
S. Langerman, J. O'Rourke, V. Pinciu, S. Ramaswami, V. Sacristan, and
S. Wuhrer.
Realistic reconfiguration of crystalline (and telecube) robots.
In Proceedings of the Workshop on the Algorithmic Foundations of
Robotics (WAFR'08), 2008.
|
|
[49]
|
P. Bose, P. Carmi, S. Collette, and M. Smid.
On the stretch factor of convex delaunay graphs.
In Proceedings of the International Symposium on Algorithms and
Computation (ISAAC 2008), volume 5369 of LNCS, 2008.
[ .pdf ]
|
|
[50]
|
G. Aloupis, S. Collette, E. D. Demaine, S. Langerman, V. Sacristan, and
S. Wuhrer.
Reconfiguration of cube-style modular robots using O(log n)
parallel moves.
In Proceedings of the International Symposium on Algorithms and
Computation (ISAAC 2008), volume 5369 of LNCS, 2008.
|
|
[51]
|
G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky.
Coloring geometric range spaces.
In Proceedings of the 8th Latin American Theoretical Informatics
(LATIN'08), volume 4957 of LNCS, 2008.
[ DOI |
.pdf ]
|
|
[52]
|
S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin.
Distribution-sensitive point location in convex subdivisions.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
(SODA'08), 2008.
[ .pdf ]
|
|
[53]
|
J. Cardinal and E. Levy.
Connected vertex covers in dense graphs.
In Proc. International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX), volume 5171 of Lecture
Notes in Computer Science, pages 35-48. Springer-Verlag, 2008.
|
|
[54]
|
E.D. Demaine, S. Langerman, and E. Price.
Confluently persistent tries for efficient version control.
In Proceedings of the 11th Scandinavian Workshop on Algorithm
Theory, volume 5124 of LNCS, pages 160-172. Springer-Verlag, 2008.
[ DOI ]
|
|
[55]
|
P. Bose, V. Dujmovic, F. Hurtado, S. Langerman, P. Morin, and D.R. Wood.
A polynomial bound for untangling geometric planar graphs.
In Proceedings of the International Conference on Topological
& Geometric Graph Theory (TGGT'08), volume 31 of Electronic Notes in
Discrete Mathematics, pages 213-218, 2008.
|
|
[56]
|
F. Pluquet, S. Langerman, A. Marot, and R. Wuyts.
Implementing partial persistence in object-oriented languages.
In Proceedings of the Workshop on Algorithm Engineering and
Experiments (ALENEX08), pages 37-48, 2008.
[ .pdf ]
|
|
[57]
|
P. Bose, K. Douïeb, and S. Langerman.
Dynamic optimality for skip lists and B-trees.
In Proceedings of the ACM-SIAM Symposium On Discrete Algorithms
(SODA2008), pages 1106-1114, 2008.
|
|
[58]
|
P. Bose, S. Langerman, and S. Roy.
Smallest enclosing circle centered on a query line segment.
In Proceedings of the 20th Canadian Conference on Computational
Geometry (CCCG 2008), pages 167-170, 2008.
|
|
[59]
|
G. Aloupis, P. Bose, V. Dujmovic, C. Gray, S. Langerman, and B. Speckmann.
Triangulating and guarding realistic polygons.
In Proceedings of the 20th Canadian Conference on Computational
Geometry (CCCG 2008), pages 107-110, 2008.
|
|
[60]
|
Chính T. Hoàng, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, and Xiao
Shu.
A note on k-colorability of p5-free graphs.
In Ochmanski and Tyszkiewicz [61], pages
387-394.
|
|
[61]
|
Edward Ochmanski and Jerzy Tyszkiewicz, editors.
Mathematical Foundations of Computer Science 2008, 33rd
International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008,
Proceedings, volume 5162 of Lecture Notes in Computer Science.
Springer, 2008.
|
|
[62]
|
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama.
Consistent digital rays.
In Proceedings of the 24th Symposium on Computational geometry
(SoCG'08), LNCS, pages 355-364, 2008.
[ DOI ]
|
|
[63]
|
Matias Korman and Takeshi Tokuyama.
Optimal insertion of a segment highway in a city metric.
In Proceedings of the 14th international conference on Computing
and Combinatorics (COCOON'08), LNCS, pages 611-620, 2008.
[ DOI |
.pdf ]
|
|
[64]
|
Matias Korman and Takeshi Tokuyama.
Optimal insertion of a segment highway in a city metric.
In Proc. of the 24th European Workshop on Computational
Geometry, 2008.
[ DOI |
.pdf ]
|
|
[65]
|
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama.
Consistent digital rays.
In Proc. of the 24th European Workshop on Computational
Geometry, 2008.
|
|
[66]
|
Matias Korman and Takeshi Tokuyama.
Subquadratic segment insertion.
In Proc. of the Language Automaton Symposium, 2008.
|
|
[67]
|
M. Korman and T. Tokuyama.
Optimal insertion of a segment highway in a city metric.
In Proc. of the 1st Asian Association for Algorithms and
Computation (AAAC'08), 2008.
|
|
[68]
|
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama.
Consistent digital rays.
In Proc. of the 1st Asian Association for Algorithms and
Computation (AAAC'08), 2008.
|
|
[69]
|
S.-W. Bae and M. Korman.
All farthest neighbors under the city metric.
In Proc. of the 11th Japan-Korea Joint Workshop on Algorithms
and Computation (WAAC'08), 2008.
|
|
[70]
|
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama.
Finding the maximum union of closures is np-hard, even for trees.
In Proc. of The 11th Japan-Korea Joint Workshop on Algorithms
and Computation (WAAC'08), 2008.
[ .pdf ]
|
|
[71]
|
Francisco Gomez-Martin, Perouz Taslakian, and Godfried T. Toussaint.
Evenness preserving operations on musical rhythms.
In Proceedings of the Canadian Conference on Computer Science
and Software Engineering (C3S2E '08), pages 121-123, New York, NY, USA,
2008. ACM.
|
|
[72]
|
Francisco Gomez-Martin, Perouz Taslakian, and Godfried T. Toussaint.
Convergence of the shadow sequence of inscribed polygons.
In Proceedings of the 18th Fall Workshop on Computational
Geometry (FWCG 2008), pages 10-11, October 2008.
|
|
[73]
|
Joseph O'Rourke, Perouz Taslakian, and Godfried T. Toussaint.
A pumping lemma for homometric rhythms.
In Proceedings of the 20th Canadian Conference on Computational
Geometry (CCCG 2008), pages 121-123, August 2008.
|
Recent Conference Publications
|
[1]
|
V. Dujmovic and S. Langerman.
A center transversal theorem for hyperplanes and applications to
graph drawing.
In Proceedings of the 2011 ACM Symposium on Computational
Geometry (SoCG 2011), to appear.
|
|
[2]
|
Y. Higashikawa, N. Katoh, S. Langerman, and S. Tanigawa.
Online graph exploration algorithms for cycles and trees by multiple
searchers.
In China-Japan Joint Conference on Computational Geometry,
Graphs and Applications (CGGA 2010), to appear.
|
|
[3]
|
International Symposium on Theoretical Aspects of Computer Science, STACS
2010, Nancy, France, March, 4-6, 2010, Proceedings, to appear.
|
|
[4]
|
J. M. Díaz-Bá nez, P. Pérez-Lantero, M. Korman, and I. Ventura.
Locating a service facility and a rapid transit line.
In Submitted to the XIV Spanish Meeting on Computational
Geometry, 2011.
|
|
[5]
|
J. M. Díaz-Bá nez, P. Pérez-Lantero, M. Korman, and I. Ventura.
The 1-center and 1-highway problem.
In Submitted to the XIV Spanish Meeting on Computational
Geometry, 2011.
|
|
[6]
|
M. Korman.
Yet another paper on minimizing interference on ad-hoc networks.
volume abs/1101.0565, 2011.
[ http ]
|
|
[7]
|
Jean Cardinal and Matias Korman.
Coloring planar homothets and three-dimensional hypergraphs.
In Proc. of the 27th European Workshop on Computational
Geometry, 2011.
[ http ]
|
|
[8]
|
G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine, M. L. Demaine, M. Dulieu,
R. Fabila-Monroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara,
and P. Taslakian.
Matching points with things.
In Proceedings of the 8th Latin American Theoretical Informatics
(LATIN'10), LNCS, 2010.
|
|
[9]
|
G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman,
O. Schwartz, S. Smorodinsky, and P. Taslakian.
Colorful strips.
In Proceedings of the 8th Latin American Theoretical Informatics
(LATIN'10), LNCS, 2010.
|
|
[10]
|
J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers, and J. I. Munro.
Sorting under partial information (without the ellipsoid algorithm).
In Proc. ACM Symposium on Theory of Computing (STOC), pages
359-368. ACM, 2010.
|
|
[11]
|
S.-W. Cheng, C. Knauer, S. Langerman, and M. Smid.
Approximating the average stretch factor of geometric graphs.
In Proceedings of the International Symposium on Algorithms and
Computation (ISAAC 2010), volume 5606 of LNCS, pages 37-48.
Springer-Verlag, 2010.
[ DOI ]
|
|
[12]
|
Y. Higashikawa, N. Katoh, S. Langerman, and S. Tanigawa.
Online graph exploration algorithms for cycles and trees by multiple
searchers.
In Abstracts of the 3rd Annual Meeting of the Asian Association
for Algorithms and Computation (AAAC 2010), 2010.
|
|
[13]
|
Christophe Paul and Michel Habib, editors.
Graph-Theoretic Concepts in Computer Science, 35th International
Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers,
volume 5911 of Lecture Notes in Computer Science, 2010.
|
|
[14]
|
Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Stefan Szeider, and
Dimitrios M. Thilikos.
On contracting graphs to fixed pattern graphs.
In van Leeuwen et al. [15], pages 503-514.
|
|
[15]
|
Jan van Leeuwen, Anca Muscholl, David Peleg, Jaroslav Pokorný, and Bernhard
Rumpe, editors.
SOFSEM 2010: Theory and Practice of Computer Science, 36th
Conference on Current Trends in Theory and Practice of Computer Science,
Spindleruv Mlýn, Czech Republic, January 23-29, 2010. Proceedings,
volume 5901 of Lecture Notes in Computer Science. Springer, 2010.
|
|
[16]
|
J. Fiala, M. Kamiński, B. Lidický, and D. Paulusma.
The k-in-a-path problem for claw-free graphs.
In STACS [3].
|
|
[17]
|
Sang Won Bae, Matias Korman, and Yoshio Okamoto.
The geodesic diameter of polygonal domains.
In Proc. of the 18th European Symposium on Algorithms, LNCS,
pages 500-511, 2010.
[ http ]
|
|
[18]
|
Shinya Anzai, Jinhee Chun, Ryosei Kasai, Matias Korman, and Takeshi Tokuyama.
Effect of corner information in simultaneous placement of k
rectangles and tableaux.
In Proceedings of the 16th international conference on Computing
and Combinatorics (COCOON'10), LNCS, pages 235-243, 2010.
[ .pdf ]
|
|
[19]
|
J. Cardinal and M. Korman.
Coloring planar homothets and three-dimensional hypergraphs.
volume abs/1101.0565, 2010.
[ http ]
|
|
[20]
|
Sang Won Bae, Matias Korman, and Yoshio Okamoto.
The geodesic diameter of polygonal domains.
In Proc. of the 26th European Workshop on Computational
Geometry, pages 49-52, 2010.
[ .pdf ]
|
|
[21]
|
Isabel Hubard and Perouz Taslakian.
Deflating polygons to the limit.
In Proceedings of the 22nd Canadian Conference on Computational
Geometry (CCCG 2010), pages 67-70, August 2010.
|
|
[22]
|
G. Aloupis, J. Cardinal, S. Collette, S. Langerman, D. Orden, and P. Ramos.
Decomposition of multiple coverings into more parts.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
(SODA'09), 2009.
|
|
[23]
|
Greg Aloupis, Nadia Benbernou, Mirela Damian, Erik Demaine, Robin Flatland,
John Iacono, and Stefanie Wuhrer.
Efficient reconfiguration for lattice-based modular robots.
In Proc. European Conference on Mobile Robotics, pages 81-86,
2009.
|
|
[24]
|
J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers, and J. I. Munro.
An efficient algorithm for partial order production.
In Proc. ACM Symposium on Theory of Computing (STOC), pages
93-100. ACM, 2009.
[ http ]
|
|
[25]
|
J. Cardinal, S. Fiorini, and G. Joret.
Minimum entropy combinatorial optimization problems.
In Proc. Computability in Europe (CiE), volume 5635 of
Lecture Notes in Computer Science, pages 79-88. Springer-Verlag, 2009.
[ http ]
|
|
[26]
|
J. Cardinal, E. D. Demaine, M. L. Demaine, S. Imahori, S. Langerman, and
R. Uehara.
Algorithmic folding complexity.
In Proc. International Symposium on Algorithms and Computation
(ISAAC), volume 5878 of Lecture Notes in Computer Science, pages
452-461. Springer-Verlag, 2009.
Also presented at the 7th Japan Conference on Computational Geometry
and Graphs (JCCGG09).
|
|
[27]
|
J. Cardinal, E. D. Demaine, S. Fiorini, G. Joret, I. Newman, and O. Weimann.
The stackelberg minimum spanning tree game on planar and
bounded-treewidth graphs.
In Proc. Workshop on Internet and Network Economics (WINE),
volume 5929 of Lecture Notes in Computer Science, pages 125-136.
Springer-Verlag, 2009.
|
|
[28]
|
Erik D. Demaine, Martin L. Demaine, Stefan Langerman, and Jérôme
Vervier.
Locked thick chains.
In Abstracts from the 25th European Workshop on Computational
Geometry (EuroCG 2009), pages 65-68, Brussels, Belgium, March 2009.
|
|
[29]
|
F. Pluquet, S. Langerman, and R. Wuyts.
Executing code in the past: Efficient in-memory object graph
versioning.
In Proceedings of the 2009 ACM SIGPLAN Conference on
Object-Oriented Programming Systems, Languages, and Applications
(OOPSLA'09), 2009.
|
|
[30]
|
E.D. Demaine, M.L. Demaine, V. Hart, J. Iacono, S. Langerman, and J. O'Rourke.
Continuous blooming of convex polyhedra.
In Abstracts from the 7th Japan Conference on Computational
Geometry and Graphs (JCCGG 2009), pages 123-124, 2009.
|
|
[31]
|
Pim van 't Hof, Marcin Kamiński, and Daniël Paulusma.
Finding induced paths of given parity in claw-free graphs.
In Paul and Habib [13], pages 341-352.
|
|
[32]
|
Takehiro Ito, Marcin Kamiński, and Erik D. Demaine.
Reconfiguration of list edge-colorings in a graph.
In Dehne et al. [33], pages 375-386.
|
|
[33]
|
Frank K. H. A. Dehne, Marina L. Gavrilova, Jörg-Rüdiger Sack, and
Csaba D. Tóth, editors.
Algorithms and Data Structures, 11th International Symposium,
WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings, volume 5664 of
Lecture Notes in Computer Science. Springer, 2009.
|
|
[34]
|
Takehiro Ito, Marcin Kamiński, Daniël Paulusma, and Dimitrios M.
Thilikos.
Parameterizing cut sets in a graph by the number of their components.
In Dong et al. [36], pages 605-615.
|
|
[35]
|
Petr A. Golovach, Marcin Kamiński, Daniël Paulusma, and Dimitrios M.
Thilikos.
Induced packing of odd cycles in a planar graph.
In Dong et al. [36], pages 514-523.
|
|
[36]
|
Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors.
Algorithms and Computation, 20th International Symposium, ISAAC
2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, volume 5878
of Lecture Notes in Computer Science. Springer, 2009.
|
|
[37]
|
Jinhee Chun, Kasai Ryosei, Matias Korman, and Takeshi Tokuyama.
Algorithms for computing the maximum weight region decomposable into
elementary shapes.
In Proceedings of the 20th International Symposium on Algorithms
and Computation (ISAAC'09), LNCS, pages 1166-1174, 2009.
[ DOI |
.pdf ]
|
|
[38]
|
Sang Won Bae, Matias Korman, and Takeshi Tokuyama.
All farthest neighbors in the presence of highways and obstacles.
In Proceedings of the 3rd International Workshop on Algorithms
and Computation (WALCOM'09), LNCS, pages 71-82, 2009.
[ DOI |
.pdf ]
|
|
[39]
|
Hee Kap Ahn, Sang Won Bae, Sang Sub Kim, Matias Korman, Iris Reinbacher, and
Wanbin Son.
Square and rectangle covering with outliers.
In Proceedings of the 3rd Frontiers of Algorithmics Workshop
(FAW'09), LNCS, 2009.
[ DOI |
http ]
|
|
[40]
|
Hee Kap Ahn, Sang Won Bae, Sang Sub Kim, Matias Korman, Iris Reinbacher, and
Wanbin Son.
Square and rectangle covering with outliers.
In Proc. of the 25th European Workshop on Computational
Geometry, 2009.
|
|
[41]
|
Matias Korman and Takeshi Tokuyama.
An improved algorithm for inserting a highway in a city metric based
on quasiconvex optimization techniques.
In Proc. of the 25th European Workshop on Computational
Geometry, 2009.
[ .pdf ]
|
|
[42]
|
M. Korman and T. Tokuyama.
An improved algorithm for inserting a highway in a city metric based
on quasiconvex optimization techniques.
In Proc. of the 2nd Asian Association for Algorithms and
Computation (AAAC'09), 2009.
|
|
[43]
|
Jinhee Chun, Kasai Ryosei, Matias Korman, and Takeshi Tokuyama.
Algorithms for computing the optimal image segmentation of
nonintersecting union of base monotone regions (in japanese).
In Proc. of the 8th Forum on Information Technology (FIT'09),
2009.
[ .pdf ]
|
|
[44]
|
Hee Kap Ahn, Sang Won Bae, Sang Sub Kim, Matias Korman, Iris Reinbacher, and
Wanbin Son.
Square and rectangle covering with outliers.
In Proc. of the Language Automaton Symposium, 2009.
|
|
[45]
|
M. Korman and T. Tokuyama.
An improved algorithm for inserting a highway in a city metric based
on quasiconvex optimization.
In IEICE technical report. Theoretical foundations of Computing
(compKEN), 2009.
|
|
[46]
|
Jinhee Chun, Kasai Ryosei, Matias Korman, and Takeshi Tokuyama.
Algorithms for optimal segmentation of regions decomposable into
basic shapes.
In IEICE technical report. Theoretical foundations of Computing
(compKEN), 2009.
|
|
[47]
|
David Bremner, Erik D. Demaine, Perouz Taslakian, and Godfried T. Toussaint.
Reconstructing points on a circle from labeled distances.
In Proceedings of the 25th European Workshop on Computational
Geometry (EuroCG 2009), pages 155-158, March 2009.
|
|
[48]
|
G. Aloupis, S. Collette, M. Damian, E. Demaine, D. El-Khechen, R. Flatland,
S. Langerman, J. O'Rourke, V. Pinciu, S. Ramaswami, V. Sacristan, and
S. Wuhrer.
Realistic reconfiguration of crystalline (and telecube) robots.
In Proceedings of the Workshop on the Algorithmic Foundations of
Robotics (WAFR'08), 2008.
|
|
[49]
|
P. Bose, P. Carmi, S. Collette, and M. Smid.
On the stretch factor of convex delaunay graphs.
In Proceedings of the International Symposium on Algorithms and
Computation (ISAAC 2008), volume 5369 of LNCS, 2008.
[ .pdf ]
|
|
[50]
|
G. Aloupis, S. Collette, E. D. Demaine, S. Langerman, V. Sacristan, and
S. Wuhrer.
Reconfiguration of cube-style modular robots using O(log n)
parallel moves.
In Proceedings of the International Symposium on Algorithms and
Computation (ISAAC 2008), volume 5369 of LNCS, 2008.
|
|
[51]
|
G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky.
Coloring geometric range spaces.
In Proceedings of the 8th Latin American Theoretical Informatics
(LATIN'08), volume 4957 of LNCS, 2008.
[ DOI |
.pdf ]
|
|
[52]
|
S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin.
Distribution-sensitive point location in convex subdivisions.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
(SODA'08), 2008.
[ .pdf ]
|
|
[53]
|
J. Cardinal and E. Levy.
Connected vertex covers in dense graphs.
In Proc. International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX), volume 5171 of Lecture
Notes in Computer Science, pages 35-48. Springer-Verlag, 2008.
|
|
[54]
|
E.D. Demaine, S. Langerman, and E. Price.
Confluently persistent tries for efficient version control.
In Proceedings of the 11th Scandinavian Workshop on Algorithm
Theory, volume 5124 of LNCS, pages 160-172. Springer-Verlag, 2008.
[ DOI ]
|
|
[55]
|
P. Bose, V. Dujmovic, F. Hurtado, S. Langerman, P. Morin, and D.R. Wood.
A polynomial bound for untangling geometric planar graphs.
In Proceedings of the International Conference on Topological
& Geometric Graph Theory (TGGT'08), volume 31 of Electronic Notes in
Discrete Mathematics, pages 213-218, 2008.
|
|
[56]
|
F. Pluquet, S. Langerman, A. Marot, and R. Wuyts.
Implementing partial persistence in object-oriented languages.
In Proceedings of the Workshop on Algorithm Engineering and
Experiments (ALENEX08), pages 37-48, 2008.
[ .pdf ]
|
|
[57]
|
P. Bose, K. Douïeb, and S. Langerman.
Dynamic optimality for skip lists and B-trees.
In Proceedings of the ACM-SIAM Symposium On Discrete Algorithms
(SODA2008), pages 1106-1114, 2008.
|
|
[58]
|
P. Bose, S. Langerman, and S. Roy.
Smallest enclosing circle centered on a query line segment.
In Proceedings of the 20th Canadian Conference on Computational
Geometry (CCCG 2008), pages 167-170, 2008.
|
|
[59]
|
G. Aloupis, P. Bose, V. Dujmovic, C. Gray, S. Langerman, and B. Speckmann.
Triangulating and guarding realistic polygons.
In Proceedings of the 20th Canadian Conference on Computational
Geometry (CCCG 2008), pages 107-110, 2008.
|
|
[60]
|
Chính T. Hoàng, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, and Xiao
Shu.
A note on k-colorability of p5-free graphs.
In Ochmanski and Tyszkiewicz [61], pages
387-394.
|
|
[61]
|
Edward Ochmanski and Jerzy Tyszkiewicz, editors.
Mathematical Foundations of Computer Science 2008, 33rd
International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008,
Proceedings, volume 5162 of Lecture Notes in Computer Science.
Springer, 2008.
|
|
[62]
|
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama.
Consistent digital rays.
In Proceedings of the 24th Symposium on Computational geometry
(SoCG'08), LNCS, pages 355-364, 2008.
[ DOI ]
|
|
[63]
|
Matias Korman and Takeshi Tokuyama.
Optimal insertion of a segment highway in a city metric.
In Proceedings of the 14th international conference on Computing
and Combinatorics (COCOON'08), LNCS, pages 611-620, 2008.
[ DOI |
.pdf ]
|
|
[64]
|
Matias Korman and Takeshi Tokuyama.
Optimal insertion of a segment highway in a city metric.
In Proc. of the 24th European Workshop on Computational
Geometry, 2008.
[ DOI |
.pdf ]
|
|
[65]
|
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama.
Consistent digital rays.
In Proc. of the 24th European Workshop on Computational
Geometry, 2008.
|
|
[66]
|
Matias Korman and Takeshi Tokuyama.
Subquadratic segment insertion.
In Proc. of the Language Automaton Symposium, 2008.
|
|
[67]
|
M. Korman and T. Tokuyama.
Optimal insertion of a segment highway in a city metric.
In Proc. of the 1st Asian Association for Algorithms and
Computation (AAAC'08), 2008.
|
|
[68]
|
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama.
Consistent digital rays.
In Proc. of the 1st Asian Association for Algorithms and
Computation (AAAC'08), 2008.
|
|
[69]
|
S.-W. Bae and M. Korman.
All farthest neighbors under the city metric.
In Proc. of the 11th Japan-Korea Joint Workshop on Algorithms
and Computation (WAAC'08), 2008.
|
|
[70]
|
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama.
Finding the maximum union of closures is np-hard, even for trees.
In Proc. of The 11th Japan-Korea Joint Workshop on Algorithms
and Computation (WAAC'08), 2008.
[ .pdf ]
|
|
[71]
|
Francisco Gomez-Martin, Perouz Taslakian, and Godfried T. Toussaint.
Evenness preserving operations on musical rhythms.
In Proceedings of the Canadian Conference on Computer Science
and Software Engineering (C3S2E '08), pages 121-123, New York, NY, USA,
2008. ACM.
|
|
[72]
|
Francisco Gomez-Martin, Perouz Taslakian, and Godfried T. Toussaint.
Convergence of the shadow sequence of inscribed polygons.
In Proceedings of the 18th Fall Workshop on Computational
Geometry (FWCG 2008), pages 10-11, October 2008.
|
|
[73]
|
Joseph O'Rourke, Perouz Taslakian, and Godfried T. Toussaint.
A pumping lemma for homometric rhythms.
In Proceedings of the 20th Canadian Conference on Computational
Geometry (CCCG 2008), pages 121-123, August 2008.
|
|
