Dijk, Thomas van - Lehrstuhl für Informatik I - Algorithmen und Komplexität

Lehrstuhl für Informatik I
Universität Würzburg
Am Hubland
D-97074 Würzburg

Raum: 01.002, Gebäude M4

Tel.: +49 (0) 931-31-89040
Fax: +49 (0) 931-31-825200

Email: thomas.van.dijk@uni-wuerzburg.de

Twitter:	@tvdmaps	GitHub:	tcvdijk
Youtube:

Forschung

Algorithmically-guided user interaction
Algorithms for Geographic Information Systems
Implementation; computational experiments
Exact algorithms (exponential-time / parameterised ...)

Awards

2. Platz aus 15 ($300), ACM SIGSPATIAL Cup 2018. For “Wüpstream: efficient enumeration of upstream features (GIS cup),’’ with Tobias Greiner, Bas den Heijer, Nadja Henning, Felix Klesen, and Andre Löffler.
Best Fast-forward Presentation at ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2018. For “Realtime linear cartograms and metro maps,” with Dieter Lutz.
Shortlist Junges Kolleg (Bayerische Akademie der Wissenschaften), Jahrgang 2017.
ACM Computing Review’s “Best of Computing” list of notable publications, 2016. For ”Matching Labels and Markers in Historical Maps: An Algorithm with
Interactive Postprocessing,” with Benedikt Budig and Alexander Wolff.
Best Paper award, theory track, at the International Conference on Graph Drawing and Network Visualization. For “Block Crossings in Storyline Visualizations.” with Martin Fink, Norbert Fischer, Fabian Lipp, Peter Markfelder, Alex Ravsky, Subhash Suri, Alexander Wolff.
Best Poster Award Runners up at ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2015 (ACMGIS) for "There and Back Again: Using Fréchet-Distance Diagrams to Find Trajectory Turning Points." with Lukas Beckmann, Benedikt Budig and Johannes Schamel.
Best Applied Paper Award at Discovery Science 2015 for "Active Learning for Classifying Template Matches in Historical Maps." [PDF] [ Video] with Benedikt Budig.
Best student contribution at Schematic Mapping 2014 for "An automated method for circular-arc metro maps." [PDF] with Arthur van Goethem and Wouter Meulemans.
Best paper at MapInteract 2014 for "Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing." with Benedikt Budig and Alexander Wolff.
Best Fast-forward Presentation and Runner-up Best Poster at ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2013 (ACMGIS) for "Accentuating Focus Maps via Partial Schematization." [PDF] with Arthur van Goethem, Jan-Henrik Haunert, Wouter Meulemans and Bettina Speckmann.
Best Short Presentation at Web and Wireless GIS 2013 (W2GIS) for "A Probabilistic Model for Road Selection in Mobile Maps" [PPT] with Jan-Henrik Haunert.

Betreuung

Doktorarbeit

Benedikt Budig. Extracting Spatial Information from Historical Maps: Algorithms and Interaction [Link beim Verlag] [digitale Version]

Masterarbeit

Maximilian Schmitt: Tourenplanung unter Berücksichtigung heterogener Metriken.
Andre Löffler: Snapping Graph Drawings to the Grid
Benedikt Budig: Algorithmische Analyse historischer Landkarten
Dieter Lutz: Realtime Linear Cartograms using Least-Squares Optimisation

Bachelorarbeit

Fabian Sieper: Zuweisen von Kantenrichtungen in Metronetzen
Julian Walter: Rotation and scale invariant template matching for historical maps
Peter Markfelder: Optimale Zeichnungen von Storylines mit Blockkreuzungen
Martin Becker: String Matching von historischen Toponymen
Fabian Feitsch: From Many User-Contributed Polygons to One Polygon Consensus
Lukas Beckmann: Analyse von Umkehrpunkten auf GPS-Trajektorien unter Verwendung der Fréchet-Distanz

Lehrveranstaltungen


SS20	Vorlesung Algorithmen für geographische Informationssysteme
	Seminar Algorithmen für Programmierwettbewerbe
WS19	Vorlesung Algorithmische Geometrie
SS19	Vorlesung Algorithmen für geographische Informationssysteme
	Seminar Algorithmen für Programmierwettbewerbe
SS18	Vorlesung Algorithmen für geographische Informationssysteme
	Seminar Visualisierung von Graphen
WS17	Vorlesung Exakte Algorithmen (vollständige Überarbeitung des Inhalts)
SS17	Vorlesung Algorithmen für geographische Informationssysteme
	Seminar Algorithmen für Programmierwettbewerbe (inkl. Konzeption)
WS16	Seminar Algorithmen zur Extraktion von Daten aus alten Landkarten
SS16	Vorlesung Algorithmen für geographische Informationssysteme
SS15	Vorlesung Algorithmen für geographische Informationssysteme
WS14	Seminar Visualisierung von geografischen Netzwerken
SS14	Vorlesung Algorithmen für geographische Informationssysteme
WS13	Übungen zu Approximationsalgorithmen
WS12	Übungen zu Algorithmen für geografische Informationssysteme
SS12	Übungen zu Exakte Algorithmen

Veröffentlichungen

[ 2020 ]
[ 2019 ]
[ 2018 ]
[ 2017 ]
[ 2016 ]
[ 2015 ]
[ 2014 ]
[ 2013 ]
[ 2011 ]
[ 2010 ]
[ 2009 ]
[ 2008 ]
[ 2007 ]

2020[ to top ]

Bundled Crossings Revisited Chaplick, Steven; van Dijk, Thomas C.; Kryven, Myroslav; Park, Ji-Won; Ravsky, Alexander; Wolff, Alexander in Journal of Graph Algorithms \& Applications (2020). 35 pages.
- [ Abstract ]
- [ BibTeX ]
An effective way to reduce clutter in a graph drawing that has (many) crossings is to group edges that travel in parallel into bundles. Each edge can participate in many such bundles. Any crossing in this bundled graph occurs between two bundles, i.e., as a bundled crossing. We consider the problem of bundled crossing minimization: A graph is given and the goal is to find a bundled drawing with at most $k$ bundled crossings. We show that the problem is NP-hard when we require a simple drawing. Our main result is an FPT algorithm (in $k$) for simple circular layouts where vertices must be placed on a circle and edges must be drawn inside the circle. These results make use of the connection between bundled crossings and graph genus. We also consider bundling crossings in a given drawing, in particular for storyline visualizations.

@article{cdkprw-bcr-JGAA20, abstract = {An effective way to reduce clutter in a graph drawing that has (many) crossings is to group edges that travel in parallel into bundles. Each edge can participate in many such bundles. Any crossing in this bundled graph occurs between two bundles, i.e., as a bundled crossing. We consider the problem of bundled crossing minimization: A graph is given and the goal is to find a bundled drawing with at most $k$ bundled crossings. We show that the problem is NP-hard when we require a simple drawing. Our main result is an FPT algorithm (in $k$) for simple circular layouts where vertices must be placed on a circle and edges must be drawn inside the circle. These results make use of the connection between bundled crossings and graph genus. We also consider bundling crossings in a given drawing, in particular for storyline visualizations.}, author = {Chaplick, Steven and van Dijk, Thomas C. and Kryven, Myroslav and Park, Ji-Won and Ravsky, Alexander and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {vgiscience}, pages = {35 pages}, title = {Bundled Crossings Revisited}, year = 2020 }

2019[ to top ]

Practical Topologically Safe Rounding of Geographic Networks van Dijk, Thomas C.; Löffler, Andre in Proceedings of the 27th {ACM} {SIGSPATIAL} International Conference on Advances in Geographic Information Systems, F. B. Kashani, G. Trajcevski, R. H. Güting, L. Kulik, S. D. Newsam (eds.) (2019). 239–248.
- [ BibTeX ]
- [ URL ]
@inproceedings{van_Dijk_2019, author = {van Dijk, Thomas C. and Löffler, Andre}, booktitle = {Proceedings of the 27th {ACM} {SIGSPATIAL} International Conference on Advances in Geographic Information Systems}, editor = {Kashani, Farnoush Banaei and Trajcevski, Goce and Güting, Ralf Hartmut and Kulik, Lars and Newsam, Shawn D.}, keywords = {vgiscience}, month = {nov}, pages = {239-248}, publisher = {{ACM}}, title = {Practical Topologically Safe Rounding of Geographic Networks}, year = 2019 }
Algorithmically-Assisted Metro Map Design van Dijk, Thomas C. in Proc. 2nd Schematic Mapping Workshop (SMW 2019), M. Roberts, M. Nöllenburg (eds.) (2019).
- [ BibTeX ]
@inproceedings{vandijk2019algorithmicallyassisted, author = {van Dijk, Thomas C.}, booktitle = {Proc. 2nd Schematic Mapping Workshop (SMW 2019)}, editor = {Roberts, Max and Nöllenburg, Martin}, keywords = {myown}, title = {Algorithmically-Assisted Metro Map Design}, year = 2019 }
Bundled Crossings Revisited. Chaplick, Steven; van Dijk, Thomas C.; Kryven, Myroslav; won Park, Ji; Ravsky, Alexander; Wolff, Alexander in 35th European Workshop on Computational Geometry (EuroCG 19) (2019).
- [ BibTeX ]
- [ URL ]
@inproceedings{chaplick2018bundled, author = {Chaplick, Steven and van Dijk, Thomas C. and Kryven, Myroslav and won Park, Ji and Ravsky, Alexander and Wolff, Alexander}, booktitle = {35th European Workshop on Computational Geometry (EuroCG 19)}, keywords = {myown}, title = {Bundled Crossings Revisited.}, year = 2019 }

2018[ to top ]

Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity Chan, Timothy M.; van Dijk, Thomas C.; Fleszar, Krzysztof; Spoerhase, Joachim; Wolff, Alexander in Proc. 29th Ann. Int. Symp. Algorithms Comput. (ISAAC’18), LIPIcs (2018). (Vol. 123) 61:1–61:13.
- [ BibTeX ]
- [ URL ]
@inproceedings{stabbing-18, author = {Chan, Timothy M. and van Dijk, Thomas C. and Fleszar, Krzysztof and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 29th Ann. Int. Symp. Algorithms Comput. (ISAAC'18)}, keywords = {myown}, pages = {61:1–61:13}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {LIPIcs}, title = {Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity}, volume = 123, year = 2018 }
Aktives Lernen f{\"u}r Informationsextraktion aus historischen Karten van Dijk, Thomas C. in Flächennutzungsmonitoring X, IOER, G. Meinel, U. Schumacher, M. Behnisch, T. Kr{\"u}ger (eds.) (2018). (Vol. 76) 181–186.
- [ BibTeX ]
- [ URL ]
@inproceedings{Dijk18aktives, author = {van Dijk, Thomas C.}, booktitle = {Flächennutzungsmonitoring X}, editor = {Meinel, Gotthard and Schumacher, Ulrich and Behnisch, Martin and Kr{\"u}ger, Tobias}, keywords = {vgiscience}, pages = {181-186}, publisher = {RHOMBOS}, series = {IOER}, title = {Aktives Lernen f{\"u}r Informationsextraktion aus historischen Karten}, volume = 76, year = 2018 }
Realtime linear cartograms and metro maps. van Dijk, Thomas C.; Lutz, Dieter in SIGSPATIAL/GIS, F. Banaei-Kashani, E. G. Hoel, R. H. Güting, R. Tamassia, L. Xiong (eds.) (2018). 488–491.
- [ BibTeX ]
- [ URL ]
@inproceedings{conf/gis/DijkL18, author = {van Dijk, Thomas C. and Lutz, Dieter}, booktitle = {SIGSPATIAL/GIS}, crossref = {conf/gis/2018}, editor = {Banaei-Kashani, Farnoush and Hoel, Erik G. and Güting, Ralf Hartmut and Tamassia, Roberto and Xiong, Li}, keywords = {vgiscience}, pages = {488-491}, publisher = {ACM}, title = {Realtime linear cartograms and metro maps.}, year = 2018 }
Wüpstream: efficient enumeration of upstream features (GIS cup). van Dijk, Thomas C.; Greiner, Tobias; den Heijer, Bas; Henning, Nadja; Klesen, Felix; Löffler, Andre in SIGSPATIAL/GIS, F. Banaei-Kashani, E. G. Hoel, R. H. Güting, R. Tamassia, L. Xiong (eds.) (2018). 626–629.
- [ BibTeX ]
- [ URL ]
@inproceedings{conf/gis/DijkGHHKL18, author = {van Dijk, Thomas C. and Greiner, Tobias and den Heijer, Bas and Henning, Nadja and Klesen, Felix and Löffler, Andre}, booktitle = {SIGSPATIAL/GIS}, crossref = {conf/gis/2018}, editor = {Banaei-Kashani, Farnoush and Hoel, Erik G. and Güting, Ralf Hartmut and Tamassia, Roberto and Xiong, Li}, keywords = {vgiscience}, pages = {626-629}, publisher = {ACM}, title = {Wüpstream: efficient enumeration of upstream features (GIS cup).}, year = 2018 }
Putting User Reputation on the Map: Unsupervised Quality Control for Crowdsourced Historical Data Barz, Björn; van Dijk, Thomas C.; Spaan, Bert; Denzler, Joachim in 2nd ACM SIGSPATIAL Workshop on Geospatial Humanities (2018).
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
In this paper we propose a novel method for quality assessment of crowdsourced data. It computes user reputation scores without requiring ground truth; instead, it is based on the consistency among users. In this pilot study, we perform some explorative data analysis on two real crowdsourcing projects by the New York Public Library: extracting building footprints as polygons from historical insurance atlases, and geolocating historical photographs. We show that the computed reputation scores are plausible and furthermore provide insight into user behavior.

@inproceedings{Barz18:Reputation, abstract = {In this paper we propose a novel method for quality assessment of crowdsourced data. It computes user reputation scores without requiring ground truth; instead, it is based on the consistency among users. In this pilot study, we perform some explorative data analysis on two real crowdsourcing projects by the New York Public Library: extracting building footprints as polygons from historical insurance atlases, and geolocating historical photographs. We show that the computed reputation scores are plausible and furthermore provide insight into user behavior.}, author = {Barz, Björn and van Dijk, Thomas C. and Spaan, Bert and Denzler, Joachim}, booktitle = {2nd ACM SIGSPATIAL Workshop on Geospatial Humanities}, keywords = {vgiscience}, title = {Putting User Reputation on the Map: Unsupervised Quality Control for Crowdsourced Historical Data}, year = 2018 }

2017[ to top ]

Journeys of the Past: A Hidden Markov Approach to Georeferencing Historical Itineraries. Budig, Benedikt; van Dijk, Thomas C. in GIR’17 Proceedings of the 11th Workshop on Geographic Information Retrieval, C. B. Jones, R. S. Purves (eds.) (2017). 7:1–7:10.
- [ BibTeX ]
- [ URL ]
@inproceedings{conf/gir/BudigD17, author = {Budig, Benedikt and van Dijk, Thomas C.}, booktitle = {GIR'17 Proceedings of the 11th Workshop on Geographic Information Retrieval}, crossref = {conf/gir/2017}, editor = {Jones, Christopher B. and Purves, Ross S.}, keywords = {vgiscience}, pages = {7:1-7:10}, publisher = {ACM}, title = {Journeys of the Past: A Hidden Markov Approach to Georeferencing Historical Itineraries.}, year = 2017 }
Algorithmically-Guided User Interaction van Dijk, Thomas C.; Wolff, Alexander in SIGSPATIAL’17 Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, E. Hoel, S. D. Newsam, S. Ravada, R. Tamassia, G. Trajcevski (eds.) (2017). 11:1–11:4.
- [ BibTeX ]
- [ URL ]
@inproceedings{conf/gis/DijkW17, author = {van Dijk, Thomas C. and Wolff, Alexander}, booktitle = {SIGSPATIAL'17 Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems}, crossref = {conf/gis/2017}, editor = {Hoel, Erik and Newsam, Shawn D. and Ravada, Siva and Tamassia, Roberto and Trajcevski, Goce}, keywords = {vgiscience}, pages = {11:1-11:4}, publisher = {ACM}, title = {Algorithmically-Guided User Interaction}, year = 2017 }
Block Crossings in Storyline Visualizations van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander in Journal of Graph Algorithms \& Applications, (Y. Hu; M. Nöllenburg, eds.) (2017). 21(5) 873–913.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.

@article{dfflmrsw-bcisv-JGAA17, abstract = {Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.}, author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander}, editor = {Hu, Yifan and Nöllenburg, Martin}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 5, pages = {873–913}, title = {Block Crossings in Storyline Visualizations}, volume = 21, year = 2017 }
Computing Storyline Visualizations with Few Block Crossings. van Dijk, Thomas C.; Lipp, Fabian; Markfelder, Peter; Wolff, Alexander in Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization, (F. Frati; K.-L. Ma, eds.) (2017).
- [ BibTeX ]
- [ URL ]
@article{journals/corr/abs-1709-01055, author = {van Dijk, Thomas C. and Lipp, Fabian and Markfelder, Peter and Wolff, Alexander}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, journal = {Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization}, keywords = {myown}, title = {Computing Storyline Visualizations with Few Block Crossings.}, year = 2017 }

2016[ to top ]

Location-dependent generalization of road networks based on equivalent destinations. van Dijk, Thomas C.; Haunert, Jan-Henrik; Oehrlein, Johannes in Comput. Graph. Forum (2016). 35(3) 451–460.
- [ BibTeX ]
- [ URL ]
@article{journals/cgf/DijkHO16, author = {van Dijk, Thomas C. and Haunert, Jan-Henrik and Oehrlein, Johannes}, journal = {Comput. Graph. Forum}, keywords = {myown}, number = 3, pages = {451-460}, title = {Location-dependent generalization of road networks based on equivalent destinations.}, volume = 35, year = 2016 }
Block Crossings in Storyline Visualizations van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alex; Suri, Subhash; Wolff, Alexander in Proc. 24nd Int. Sympos. Graph Drawing (2016).
- [ BibTeX ]
- [ URL ]
@article{vandijk2016block, author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alex and Suri, Subhash and Wolff, Alexander}, journal = {Proc. 24nd Int. Sympos. Graph Drawing}, keywords = {myown}, note = {(to appear) Best paper award.}, title = {Block Crossings in Storyline Visualizations}, year = 2016 }
Snapping Graph Drawings to the Grid Optimally Löffler, Andre; van Dijk, Thomas C.; Wolff, Alexander in Proc. 24nd Int. Sympos. Graph Drawing (2016).
- [ BibTeX ]
- [ URL ]
@article{loffler2016snapping, author = {Löffler, Andre and van Dijk, Thomas C. and Wolff, Alexander}, journal = {Proc. 24nd Int. Sympos. Graph Drawing}, keywords = {myown}, note = {(to appear)}, title = {Snapping Graph Drawings to the Grid Optimally}, year = 2016 }
Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing Budig, Benedikt; van Dijk, Thomas C.; Wolff, Alexander in Transactions on Spatial Algorithms and Systems (2016).
- [ BibTeX ]
- [ URL ]
@article{budig2016matching, author = {Budig, Benedikt and van Dijk, Thomas C. and Wolff, Alexander}, journal = {Transactions on Spatial Algorithms and Systems}, keywords = {myown}, note = {(to appear)}, title = {Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing}, year = 2016 }
Glyph Miner: A System for Efficiently Extracting Glyphs from Early Prints in the Context of OCR. Budig, Benedikt; van Dijk, Thomas C.; Kirchner, Felix in Proceedings of the 16th ACM/IEEE-CS on Joint Conference on Digital Libraries, JCDL ’16, N. R. Adam, L. (Boots) Cassel, Y. Yesha, R. Furuta, M. C. Weigle (eds.) (2016). 31–34.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
While off-the-shelf OCR systems work well on many modern documents, the heterogeneity of early prints provides a significant challenge. To achieve good recognition quality, existing software must be "trained" specifically to each particular corpus. This is a tedious process that involves significant user effort. In this paper we demonstrate a system that generically replaces a common part of the training pipeline with a more efficient workflow: Given a set of scanned pages of a historical document, our system uses an efficient user interaction to semi-automatically extract large numbers of occurrences of glyphs indicated by the user. In a preliminary case study, we evaluate the effectiveness of our approach by embedding our system into the workflow at the University Library Würzburg.

@inproceedings{conf/jcdl/BudigDK16, abstract = {While off-the-shelf OCR systems work well on many modern documents, the heterogeneity of early prints provides a significant challenge. To achieve good recognition quality, existing software must be "trained" specifically to each particular corpus. This is a tedious process that involves significant user effort. In this paper we demonstrate a system that generically replaces a common part of the training pipeline with a more efficient workflow: Given a set of scanned pages of a historical document, our system uses an efficient user interaction to semi-automatically extract large numbers of occurrences of glyphs indicated by the user. In a preliminary case study, we evaluate the effectiveness of our approach by embedding our system into the workflow at the University Library Würzburg.}, author = {Budig, Benedikt and van Dijk, Thomas C. and Kirchner, Felix}, booktitle = {Proceedings of the 16th ACM/IEEE-CS on Joint Conference on Digital Libraries}, crossref = {conf/jcdl/2016}, editor = {Adam, Nabil R. and Cassel, Lillian (Boots) and Yesha, Yelena and Furuta, Richard and Weigle, Michele C.}, keywords = {myown}, pages = {31–34}, publisher = {ACM}, series = {JCDL '16}, title = {Glyph Miner: A System for Efficiently Extracting Glyphs from Early Prints in the Context of OCR.}, year = 2016 }

2015[ to top ]

There and Back Again: Using Fréchet-Distance Diagrams to Find Trajectory Turning Points Beckmann, Lukas; Budig, Benedikt; van Dijk, Thomas C.; Schamel, Johannes in Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015) (2015). 238–241.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
There is much interest in the automatic analysis of GPS trajectories, motivated amongst others by animal tracking, traffic modelling and tourism studies. Core questions involve for example detecting stopping points and flocking behaviour, and developing routing models. In this paper we consider turning points. We develop a formal definition of "turning point" based on analysing the structure of free-space diagrams for Fréchet distance. We give an efficient algorithm for computing an optimal set of turning points under this criterion. Our method is evaluated in the context of a current study on tourist preferences at Berchtesgaden National Park, Germany. We evaluate the suitability of our definition and the efficiency of our algorithm on a large set of real-world GPS trajectories collected by outdoor recreationists. A ground truth of turning points was established by hand for the complete data set. Experiments show that the runtime and quality of our method are suitable for practical applications.

@inproceedings{beckmann2015there, abstract = {There is much interest in the automatic analysis of GPS trajectories, motivated amongst others by animal tracking, traffic modelling and tourism studies. Core questions involve for example detecting stopping points and flocking behaviour, and developing routing models. In this paper we consider turning points. We develop a formal definition of "turning point" based on analysing the structure of free-space diagrams for Fréchet distance. We give an efficient algorithm for computing an optimal set of turning points under this criterion. Our method is evaluated in the context of a current study on tourist preferences at Berchtesgaden National Park, Germany. We evaluate the suitability of our definition and the efficiency of our algorithm on a large set of real-world GPS trajectories collected by outdoor recreationists. A ground truth of turning points was established by hand for the complete data set. Experiments show that the runtime and quality of our method are suitable for practical applications.}, author = {Beckmann, Lukas and Budig, Benedikt and van Dijk, Thomas C. and Schamel, Johannes}, booktitle = {Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015)}, keywords = {myown}, pages = {238–241}, publisher = {ACM}, title = {There and Back Again: Using Fréchet-Distance Diagrams to Find Trajectory Turning Points}, year = 2015 }
Active Learning for Classifying Template Matches in Historical Maps Budig, Benedikt; Dijk, Thomas C. van in Discovery Science, Lecture Notes in Computer Science, N. Japkowicz, S. Matwin (eds.) (2015). (Vol. 9356) 33–47.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
Historical maps are important sources of information for scholars of various disciplines. Many libraries are digitising their map collections as bitmap images, but for these collections to be most useful, there is a need for searchable metadata. Due to the heterogeneity of the images, metadata are mostly extracted by hand - if at all: many collections are so large that it is important to minimise the effort spent on individual maps. We propose an active-learning approach to one of the practical problems in automatic metadata extraction from historical maps: locating occurrences of image elements such as text or place markers. For that, we combine template matching (to locate possible occurrences) with active learning (to efficiently determine a classification). Using this approach, we design a human computer interaction in which large numbers of elements on a map can be located reliably using little user effort. We experimentally demonstrate the effectiveness of this approach on real-world data.

@inproceedings{budig2015active, abstract = {Historical maps are important sources of information for scholars of various disciplines. Many libraries are digitising their map collections as bitmap images, but for these collections to be most useful, there is a need for searchable metadata. Due to the heterogeneity of the images, metadata are mostly extracted by hand - if at all: many collections are so large that it is important to minimise the effort spent on individual maps. We propose an active-learning approach to one of the practical problems in automatic metadata extraction from historical maps: locating occurrences of image elements such as text or place markers. For that, we combine template matching (to locate possible occurrences) with active learning (to efficiently determine a classification). Using this approach, we design a human computer interaction in which large numbers of elements on a map can be located reliably using little user effort. We experimentally demonstrate the effectiveness of this approach on real-world data.}, author = {Budig, Benedikt and Dijk, Thomas C. van}, booktitle = {Discovery Science}, editor = {Japkowicz, Nathalie and Matwin, Stan}, keywords = {template-matching}, note = {Best Applied Paper Award}, pages = {33-47}, publisher = {Springer International Publishing}, series = {Lecture Notes in Computer Science}, title = {Active Learning for Classifying Template Matches in Historical Maps}, volume = 9356, year = 2015 }

2014[ to top ]

Map Schematization with Circular Arcs van Dijk, Thomas C.; van Goethem, Arthur; Haunert, Jan-Henrik; Meulemans, Wouter; Speckmann, Bettina in Geographic Information Science, (M. Duckham; E. Pebesma; K. Stewart; A. Frank, eds.) (2014). 8728 1–17.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We present an algorithm to compute schematic maps with circular arcs. Our algorithm iteratively replaces two consecutive arcs with a single arc to reduce the complexity of the output map and thus to increase its level of abstraction. Our main contribution is a method for replacing arcs that meet at high-degree vertices. This allows us to greatly reduce the output complexity, even for dense networks. We experimentally evaluate the effectiveness of our algorithm in three scenarios: territorial outlines, road networks, and metro maps. For the latter, we combine our approach with an algorithm to more evenly distribute stations. Our experiments show that our algorithm produces high-quality results for territorial outlines and metro maps. However, the lack of caricature (exaggeration of typical features) makes it less useful for road networks.

@article{noKey, abstract = {We present an algorithm to compute schematic maps with circular arcs. Our algorithm iteratively replaces two consecutive arcs with a single arc to reduce the complexity of the output map and thus to increase its level of abstraction. Our main contribution is a method for replacing arcs that meet at high-degree vertices. This allows us to greatly reduce the output complexity, even for dense networks. We experimentally evaluate the effectiveness of our algorithm in three scenarios: territorial outlines, road networks, and metro maps. For the latter, we combine our approach with an algorithm to more evenly distribute stations. Our experiments show that our algorithm produces high-quality results for territorial outlines and metro maps. However, the lack of caricature (exaggeration of typical features) makes it less useful for road networks.}, author = {van Dijk, Thomas C. and van Goethem, Arthur and Haunert, Jan-Henrik and Meulemans, Wouter and Speckmann, Bettina}, booktitle = {Geographic Information Science}, editor = {Duckham, Matt and Pebesma, Edzer and Stewart, Kathleen and Frank, AndrewU.}, keywords = {myown}, pages = {1-17}, publisher = {Springer International Publishing}, series = {Lecture Notes in Computer Science}, title = {Map Schematization with Circular Arcs}, volume = 8728, year = 2014 }
Inclusion/Exclusion Meets Measure and Conquer Nederlof, Jesper; van Rooij, Johan M.M.; van Dijk, Thomas C. in Algorithmica (2014). 69(3) 685–740.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
Inclusion/exclusion and measure and conquer are two central techniques from the field of exact exponential-time algorithms that recently received a lot of attention. In this paper, we show that both techniques can be used in a single algorithm. This is done by looking at the principle of inclusion/exclusion as a branching rule. This inclusion/exclusion-based branching rule can be combined in a branch-and-reduce algorithm with traditional branching rules and reduction rules. The resulting algorithms can be analysed using measure and conquer allowing us to obtain good upper bounds on their running times.

@article{noKey, abstract = {Inclusion/exclusion and measure and conquer are two central techniques from the field of exact exponential-time algorithms that recently received a lot of attention. In this paper, we show that both techniques can be used in a single algorithm. This is done by looking at the principle of inclusion/exclusion as a branching rule. This inclusion/exclusion-based branching rule can be combined in a branch-and-reduce algorithm with traditional branching rules and reduction rules. The resulting algorithms can be analysed using measure and conquer allowing us to obtain good upper bounds on their running times.}, author = {Nederlof, Jesper and van Rooij, Johan M.M. and van Dijk, Thomas C.}, journal = {Algorithmica}, keywords = {myown}, number = 3, pages = {685-740}, publisher = {Springer US}, title = {Inclusion/Exclusion Meets Measure and Conquer}, volume = 69, year = 2014 }
An Automated Method for Circular-Arc Metro Maps van Dijk, T. C.; van Goethem, A.; Haunert, J.H.; Meulemans, W.; Speckmann, B. in Schematic Mapping (2014).
- [ BibTeX ]
@article{vandijk2014automated, author = {van Dijk, T. C. and van Goethem, A. and Haunert, J.H. and Meulemans, W. and Speckmann, B.}, journal = {Schematic Mapping}, keywords = {myown}, title = {An Automated Method for Circular-Arc Metro Maps}, year = 2014 }
Improved Approximation Algorithms for Box Contact Representations Bekos, Michael A.; van Dijk, Thomas C.; Fink, Martin; Kindermann, Philipp; Kobourov, Stephen G.; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander in Proc. 22th Annual European Symposium on Algorithms (ESA’14) (2014). 87–99.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks (Crown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, Max-Crown, in which realizing each desired adjacency yields a certain profit. We show that the problem is APX-complete on bipartite graphs of bounded maximum degree. We present the first O(1)-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we consider several planar graph classes (stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit.

@inproceedings{bdfkkpsw14, abstract = {We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks (Crown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, Max-Crown, in which realizing each desired adjacency yields a certain profit. We show that the problem is APX-complete on bipartite graphs of bounded maximum degree. We present the first O(1)-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we consider several planar graph classes (stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit.}, author = {Bekos, Michael A. and van Dijk, Thomas C. and Fink, Martin and Kindermann, Philipp and Kobourov, Stephen G. and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 22th Annual European Symposium on Algorithms (ESA'14)}, keywords = {myown}, pages = {87–99}, title = {Improved Approximation Algorithms for Box Contact Representations}, year = 2014 }
Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing Budig, B.; van Dijk, T. C.; Wolff, A. in Proceedings of the 2nd ACM SIGSPATIAL International Workshop on MapInteraction (2014).
- [ Abstract ]
- [ BibTeX ]
In this paper we present an algorithmic system for determining the proper correspondence between place markers and their labels in historical maps. We assume that the locations of place markers (usually pictographs) and labels (pieces of text) have already been determined---either algorithmically or by hand---and want to match the labels to the markers. This time-consuming step in the digitization process of historical maps is non-trivial even for humans, but provides valuable metadata (for example when subsequently georeferencing the map). In order to speed up this process, we model the problem in terms of combinatorial optimization, solve that problem efficiently, and show how user interaction can be used to improve the quality of results. We test the algorithm on a manually-extracted ground truth for two historical maps with a combined total of over 4000 markers and labels. The algorithm correctly matches 99% of the labels and is robust against noisy input. It furthermore performs a sensitivity analysis and in this way computes a measure of confidence for each of the assignments. We use this as the basis of an interactive system, where the user's effort is directed to checking the parts of the map where the algorithm is unsure; any corrections the user makes can be propagated by the algorithm. We discuss an early prototype of this system and statistically confirm that it successfully locates the areas on the map where the algorithm needs help.

@article{budig2014matching, abstract = {In this paper we present an algorithmic system for determining the proper correspondence between place markers and their labels in historical maps. We assume that the locations of place markers (usually pictographs) and labels (pieces of text) have already been determined—either algorithmically or by hand—and want to match the labels to the markers. This time-consuming step in the digitization process of historical maps is non-trivial even for humans, but provides valuable metadata (for example when subsequently georeferencing the map). In order to speed up this process, we model the problem in terms of combinatorial optimization, solve that problem efficiently, and show how user interaction can be used to improve the quality of results. We test the algorithm on a manually-extracted ground truth for two historical maps with a combined total of over 4000 markers and labels. The algorithm correctly matches 99% of the labels and is robust against noisy input. It furthermore performs a sensitivity analysis and in this way computes a measure of confidence for each of the assignments. We use this as the basis of an interactive system, where the user's effort is directed to checking the parts of the map where the algorithm is unsure; any corrections the user makes can be propagated by the algorithm. We discuss an early prototype of this system and statistically confirm that it successfully locates the areas on the map where the algorithm needs help.}, author = {Budig, B. and van Dijk, T. C. and Wolff, A.}, journal = {Proceedings of the 2nd ACM SIGSPATIAL International Workshop on MapInteraction}, keywords = {myown}, note = {Best paper.}, title = {Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing}, year = 2014 }
How to Eat a Graph: Computing Selection Sequences for the Continuous Generalization of Road Networks Chimani, M.; van Dijk, T. C.; Haunert, J.-H. in Proceedings of the 22st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (2014). (Vol. 28) 243–252.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
In a connected weighted graph, consider deleting the edges one at a time, in some order, such that after every deletion the remaining edges are still connected. We study the problem of finding such a deletion sequence that maximizes the sum of the weights of the edges in all the distinct graphs generated: the weight of an edge is counted in every graph that it is in. This effectively asks for the high-weight edges to remain in the graph as long as possible, subject to connectivity. We apply this to road network generalization in order to generate a sequence of successively more generalized maps of a road network so that these maps go well together, instead of considering each level of generalization independently. In particular, we look at the problem of making a road segment selection that is consistent across zoom levels. We show that the problem is NP-hard and give an integer linear program (ILP) that solves it optimally. Solving this ILP is only feasible for small instances. Next we develop constant-factor approximation algorithms and heuristics. We experimentally demonstrate that these heuristics perform well on real-world instances.

@inproceedings{chimani2014graph, abstract = {In a connected weighted graph, consider deleting the edges one at a time, in some order, such that after every deletion the remaining edges are still connected. We study the problem of finding such a deletion sequence that maximizes the sum of the weights of the edges in all the distinct graphs generated: the weight of an edge is counted in every graph that it is in. This effectively asks for the high-weight edges to remain in the graph as long as possible, subject to connectivity. We apply this to road network generalization in order to generate a sequence of successively more generalized maps of a road network so that these maps go well together, instead of considering each level of generalization independently. In particular, we look at the problem of making a road segment selection that is consistent across zoom levels. We show that the problem is NP-hard and give an integer linear program (ILP) that solves it optimally. Solving this ILP is only feasible for small instances. Next we develop constant-factor approximation algorithms and heuristics. We experimentally demonstrate that these heuristics perform well on real-world instances.}, author = {Chimani, M. and van Dijk, T. C. and Haunert, J.-H.}, journal = {Proceedings of the 22st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems}, keywords = {myown}, number = 10, pages = {243-252}, title = {How to Eat a Graph: Computing Selection Sequences for the Continuous Generalization of Road Networks}, volume = 28, year = 2014 }
Interactive focus maps using least-squares optimization van Dijk, Thomas C.; Haunert, Jan-Henrik in International Journal of Geographical Information Science (2014). 28(10) 2052–2075.
- [ BibTeX ]
- [ URL ]
@article{doi:10.1080/13658816.2014.887718, author = {van Dijk, Thomas C. and Haunert, Jan-Henrik}, journal = {International Journal of Geographical Information Science}, keywords = {myown}, number = 10, pages = {2052-2075}, title = {Interactive focus maps using least-squares optimization}, volume = 28, year = 2014 }

2013[ to top ]

Accentuating Focus Maps via Partial Schematization van Dijk, Thomas C.; van Goethem, Arthur; Haunert, Jan-Henrik; Meulemans, Wouter; Speckmann, Bettina in Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL’13 (2013). 428–431.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases.

@inproceedings{vanDijk:2013:AFM:2525314.2525452, abstract = {We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases.}, address = {New York, NY, USA}, author = {van Dijk, Thomas C. and van Goethem, Arthur and Haunert, Jan-Henrik and Meulemans, Wouter and Speckmann, Bettina}, booktitle = {Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems}, keywords = {myown}, pages = {428–431}, publisher = {ACM}, series = {SIGSPATIAL'13}, title = {Accentuating Focus Maps via Partial Schematization}, year = 2013 }
Road Segment Selection with Strokes and Stability van Dijk, T. C.; Fleszar, K.; Haunert, J.-H.; Spoerhase, J. in Proceedings of the 1st ACM SIGSPATIAL International Workshop on MapInteraction, MapInteract ’13 (2013). 72–77.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.

@inproceedings{vanDijk:2013:RSS:2534931.2534936, abstract = {In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.}, address = {New York, NY, USA}, author = {van Dijk, T. C. and Fleszar, K. and Haunert, J.-H. and Spoerhase, J.}, booktitle = {Proceedings of the 1st ACM SIGSPATIAL International Workshop on MapInteraction}, keywords = {myown}, pages = {72–77}, publisher = {ACM}, series = {MapInteract '13}, title = {Road Segment Selection with Strokes and Stability}, year = 2013 }
A Probabilistic Model for Road Selection in Mobile Maps van Dijk, Thomas C.; Haunert, Jan-Henrik in Web and Wireless Geographical Information Systems, S. H. Liang, X. Wang, C. Claramunt (eds.) (2013). (Vol. 7820) 214–222.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
Mobile devices provide an interesting context for map drawing. This paper presents a novel road-selection algorithm based on PageRank, the algorithm famously used by Google to rank web pages by importance. Underlying the PageRank calculation is a probabilistic model of user behavior. We provide suitable generalizations of this model to road networks. Our implementation of the proposed algorithm handles a sizable map in approximately a tenth of a second on a desktop PC. Therefore, our methods should be feasible on modern mobile devices.

@incollection{noKey, abstract = {Mobile devices provide an interesting context for map drawing. This paper presents a novel road-selection algorithm based on PageRank, the algorithm famously used by Google to rank web pages by importance. Underlying the PageRank calculation is a probabilistic model of user behavior. We provide suitable generalizations of this model to road networks. Our implementation of the proposed algorithm handles a sizable map in approximately a tenth of a second on a desktop PC. Therefore, our methods should be feasible on modern mobile devices.}, author = {van Dijk, Thomas C. and Haunert, Jan-Henrik}, booktitle = {Web and Wireless Geographical Information Systems}, editor = {Liang, Steve H.L. and Wang, Xin and Claramunt, Christophe}, keywords = {myown}, pages = {214-222}, publisher = {Springer Berlin Heidelberg}, series = {Lecture Notes in Computer Science}, title = {A Probabilistic Model for Road Selection in Mobile Maps}, volume = 7820, year = 2013 }

2011[ to top ]

Optimizing Wireless Sensor Network Flow by Column Generation van den Akker, J. M.; van Dijk, T. C.; Hoogeveen, J. A.; Toorop, T. in Conference of the European Chapter on Combinatorial Optimization (2011).
- [ BibTeX ]
@article{vandenakker2011optimizing, author = {van den Akker, J. M. and van Dijk, T. C. and Hoogeveen, J. A. and Toorop, T.}, journal = {Conference of the European Chapter on Combinatorial Optimization}, keywords = {myown}, title = {Optimizing Wireless Sensor Network Flow by Column Generation}, year = 2011 }

2010[ to top ]

A Cubic Kernel for Feedback Vertex Set and Loop Cutset Bodlaender, HansL.; van Dijk, ThomasC. in Theory of Computing Systems (2010). 46(3) 566–597.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
The

@article{noKey, abstract = {The}, author = {Bodlaender, HansL. and van Dijk, ThomasC.}, journal = {Theory of Computing Systems}, keywords = {myown}, number = 3, pages = {566-597}, publisher = {Springer-Verlag}, title = {A Cubic Kernel for Feedback Vertex Set and Loop Cutset}, volume = 46, year = 2010 }

2009[ to top ]

Inclusion/Exclusion Meets Measure and Conquer van Rooij, Johan M. M.; Nederlof, Jesper; van Dijk, Thomas C. in Algorithms - ESA 2009, A. Fiat, P. Sanders (eds.) (2009). (Vol. 5757) 554–565.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
In this paper, two central techniques from the field of exponential time algorithms are combined for the first time: inclusion/exclusion and branching with measure and conquer analysis.

@incollection{noKey, abstract = {In this paper, two central techniques from the field of exponential time algorithms are combined for the first time: inclusion/exclusion and branching with measure and conquer analysis.}, author = {van Rooij, Johan M. M. and Nederlof, Jesper and van Dijk, Thomas C.}, booktitle = {Algorithms - ESA 2009}, editor = {Fiat, Amos and Sanders, Peter}, keywords = {myown}, pages = {554-565}, publisher = {Springer Berlin Heidelberg}, series = {Lecture Notes in Computer Science}, title = {Inclusion/Exclusion Meets Measure and Conquer}, volume = 5757, year = 2009 }

2008[ to top ]

Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint Bodlaender, Hans; Tan, Richard; van Dijk, Thomas C.; van Leeuwen, Jan in Algorithm Theory - SWAT 2008, J. Gudmundsson (ed.) (2008). (Vol. 5124) 102–113.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
We study the integer maximum flow problem on wireless sensor networks with energy constraint. In this problem, sensor nodes gather data and then relay them to a base station, before they run out of battery power. Packets are considered as integral units and not splittable. The problem is to find the maximum data flow in the sensor network subject to the energy constraint of the sensors. We show that this integral version of the problem is strongly NP-complete and in fact APX-hard. It follows that the problem is unlikely to have a polynomial time approximation scheme. Even when restricted to graphs with concrete geometrically defined connectivity and transmission costs, the problem is still strongly NP-complete. We provide some interesting polynomial time algorithms that give good approximations for the general case nonetheless. For networks of bounded treewidth greater than two, we show that the problem is weakly NP-complete and provide pseudo-polynomial time algorithms. For a special case of graphs with treewidth two, we give a polynomial time algorithm.

@incollection{Bodlaender:MaxFlowEnergyConstraint, abstract = {We study the integer maximum flow problem on wireless sensor networks with energy constraint. In this problem, sensor nodes gather data and then relay them to a base station, before they run out of battery power. Packets are considered as integral units and not splittable. The problem is to find the maximum data flow in the sensor network subject to the energy constraint of the sensors. We show that this integral version of the problem is strongly NP-complete and in fact APX-hard. It follows that the problem is unlikely to have a polynomial time approximation scheme. Even when restricted to graphs with concrete geometrically defined connectivity and transmission costs, the problem is still strongly NP-complete. We provide some interesting polynomial time algorithms that give good approximations for the general case nonetheless. For networks of bounded treewidth greater than two, we show that the problem is weakly NP-complete and provide pseudo-polynomial time algorithms. For a special case of graphs with treewidth two, we give a polynomial time algorithm.}, author = {Bodlaender, Hans and Tan, Richard and van Dijk, Thomas C. and van Leeuwen, Jan}, booktitle = {Algorithm Theory - SWAT 2008}, editor = {Gudmundsson, Joachim}, keywords = {myown}, pages = {102-113}, publisher = {Springer Berlin / Heidelberg}, series = {Lecture Notes in Computer Science}, title = {Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint}, volume = 5124, year = 2008 }

2007[ to top ]

Kernelization for Loop Cutset van Dijk, T. C. (M. D. Edwin de Jong, ed.) (2007).
- [ Abstract ]
- [ BibTeX ]
Inference in probabilistic {(or: Bayesian)} networks is a problem with many applications in AI, for example in decision support systems. One way of solving it is using the method of conditioning, which requires a loop cutset of the network. Finding an optimal loop cutset for a given network is NP-hard, but building on work by Bodlaender we show it does have a kernel of cubic size. A kernelization is typically used as a first step in a 'fixed parameter tractable' algorithm, but can also be used as an ordinary preprocessing heuristic by choosing a safe value for the parameter. We have imple- mented this kernelization algorithm and experimentally demonstrate that it is both efficient and effective: it handles networks with thousands of vertices in a couple of seconds and, even when used as just a regular preprocessing heuristic, significantly speeds up the subsequent calculation of an optimal loop cutset.

@article{vandijk2007kernelization, abstract = {Inference in probabilistic {(or: Bayesian)} networks is a problem with many applications in AI, for example in decision support systems. One way of solving it is using the method of conditioning, which requires a loop cutset of the network. Finding an optimal loop cutset for a given network is NP-hard, but building on work by Bodlaender we show it does have a kernel of cubic size. A kernelization is typically used as a first step in a 'fixed parameter tractable' algorithm, but can also be used as an ordinary preprocessing heuristic by choosing a safe value for the parameter. We have imple- mented this kernelization algorithm and experimentally demonstrate that it is both efficient and effective: it handles networks with thousands of vertices in a couple of seconds and, even when used as just a regular preprocessing heuristic, significantly speeds up the subsequent calculation of an optimal loop cutset.}, author = {van Dijk, T. C.}, editor = {Edwin de Jong, Mehdi Dastani}, keywords = {myown}, title = {Kernelization for Loop Cutset}, year = 2007 }

Dr. Thomas van Dijk