Peter Damaschke

Full Professor

Computer Science and Engineering
Chalmers University of Technology
41296 Göteborg, Sweden
EDIT Building, room 5480
Email: ptr(at)chalmers.se
Phone: +46 31 772 5405

Courses

Advanced Algorithms, period 2
Algorithms, period 3

Vita

Born in 1963 in (Eastern) Germany, married, two children.
Studied mathematics in Halle and Jena, 1991 Dr. rer. nat.
1991-2000 assistant at FernUniversität Hagen.
1994 Habilitation in computer science.
Since 2000 here at Chalmers.

Interests: classical music, cooking, art, philosophy, literature, satire, history, and ... :

Research

Former and ongoing projects:

Some early results from 1990 about cographs are featured in Wikipedia.
2003-2013: three 3-years projects supported by the Swedish Research Council (VR).
2012-2016: "Data-driven secure business intelligence", supported by the Swedish Foundation for Strategic Research (SSF), with David Sands, Devdatt Dubhashi, Andrei Sabelfeld, Gerardo Schneider.
since 2016: scientific advisor at the Fraunhofer-Chalmers Research Centre for Industrial Mathematics.
2023 "Combinatorial algorithms for optimizing industrial facilities", supported by the Department
2023-2024 "Raw2Rich Graphs: Learning on-demand human actions based on graph theory", with Karinne Ramirez-Amaro, supported by the Chalmers Area of Advance ICT.

PhD students:

Leonid Molokov (co-supervisor: Devdatt Dubhashi), PhD 2013/14,
featured in Parameterized Complexity Newsletter April 2013.
Azam Sheikh Muhammad, PhD 2013.
Olof Mogren, until licentiate 2015.
Raad Salman, licentiate 2017.

Other selected scientific activities and services:

International Symposium on Bioinformatics Research and Applications ISBRA (2006-2008). PC member.
ICALP 2011 Workshop on Algorithms and Data Structures for Selection, Identification and Encoding ICALP2011GT in Zurich. PC member.
5th Emléktábla Workshop "Combinatorial Search", János Bolyai Mathematical Society and Alfréd Rényi Institute of Mathematics (Budapest) 2013. Invited lecturer
5th IEEE International Conference on Computational Advances in Bio and Medical Sciences ICCABS 2015 in Miami. PC member.
11th International Conference on Algorithmic Aspects of Information and Management AAIM 2016 in Bergamo (Italy). PC member.
The First Aachen Discrete Mathematics Days 2016, Workshop on the Occasion of Eberhard Triesch's 60th Birthday. Invited talk.
46th International Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2020 in Limassol (Cyprus). PC member, track Foundations of Algorithmic Computational Biology.
47th International Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2021 in Bolzano (Italy). PC member, track Foundations of Algorithmic Computational Biology.
12th International Conference on Algorithms and Complexity CIAC 2021 in Larnaca (Cyprus). PC member.
35th International Workshop on Combinatorial Algorithms IWOCA 2024 in Ischia (Italy). PC member.

Distinctions

2012 Best Paper Award (with Azam Sheikh Muhammad) at the 38th International Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2012.
2019 Pedagogical Prize of the IT Student Division at Chalmers (SnIT) for 2018 (and nominated also in 2011, 2016, 2018, 2020, 2025).
2020 Best Paper Award at the 31st International Workshop on Combinatorial Algorithms IWOCA 2020.

Some Publications since 2004

See also DBLP.

Branch and bound for the fixed-shape unequal area facility layout problem (open access)
with Fredrik Ekstedt and Raad Salman
Computers and Industrial Engineering 203 (2025), article 110987
On central placements of new vertices in a planar point set (open access)
with Fredrik Ekstedt and Raad Salman
Theoretical Computer Science 1025 (2025), article 114973
A linear-time optimal broadcasting algorithm in stars of cliques (open access)
Journal of Graph Algorithms and Applications 28(1) (2024), 385-388
Tandem Duplication Parameterized by the Length Difference
26th Prague Stringology Conference PSC 2023, 18-29
Proceedings
Distance-based solution of patrolling problems with individual waiting times (open access)
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems ATMOS 2021 (part of ALGO 2021), Lisbon/online, OASIcs 96, paper 14
On an ordering problem in weighted hypergraphs PDF
32nd International Workshop on Combinatorial Algorithms IWOCA 2021, Ottawa/online, LNCS 12757, 252-264
The final authenticated version is available online at DOI.
Enumerating grid layouts of graphs (open access)
Journal of Graph Algorithms and Applications 24 (2020), 433-460
Two robots patrolling on a line: Integer version and approximability PDF
*Best Paper Award* at the 31st International Workshop on Combinatorial Algorithms IWOCA 2020, Bordeaux/online, LNCS 12126, 211-223
Ordering a sparse graph to minimize the sum of right ends of edges PDF
31st International Workshop on Combinatorial Algorithms IWOCA 2020, Bordeaux/online, LNCS 12126, 224-236
Dividing splittable goods evenly and with limited fragmentation (open access)
Algorithmica 82 (2020), 1298-1328
preliminary version of parts of the paper in:
42nd International Symposium on Mathematical Foundations of Computer Science MFCS 2017, Aalborg (Denmark),
LIPIcs 83, paper 9
Branch-and-bound for the precedence constrained generalized traveling salesman problem
with Raad Salman and Fredrik Ekstedt
Operations Research Letters 48 (2020), 163-166
extended abstract in 13th Symposium on Combinatorial Search SoCS 2020, AAAI Press, 137-138
Equitable induced decompositions of twin graphs (open access)
Australasian Journal of Combinatorics 76 (2020), 24-40
Optimal partial clique edge covering guided by potential energy minimization (open access)
Optimization Letters 13 (2019), 1469-1481
Combinatorial search in two and more rounds PDF
Theoretical Computer Science 780 (2019), 1-11
Parameterized mixed graph coloring (open access)
Journal of Combinatorial Optimization 38 (2019), 362-374
Saving probe bits by cube domination PDF (full version)
44th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2018, Lübbenau near Cottbus, LNCS 11159, 139-151
The final publication is available online at DOI.
An optimization problem related to Bloom filters with bit patterns PDF (full version)
with Alexander Schliep
44th International Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2018, Krems an der Donau, LNCS 10706, 525-538
The final publication is available at Springer via DOI.
The solution space of sorting with recurring comparison faults (open access)
Theory of Computing Systems 62 (2018), 1427-1442,
Special Issue IWOCA 2016
Calculating approximation guarantees for partial set cover of pairs (open access)
Optimization Letters 11 (2017), 1293-1302
Finding defectives on a line by random docking and interval group tests PDF
Discrete Mathematics, Algorithms and Applications 9 (2017), paper 1750029
Refined algorithms for hitting many intervals PDF
Information Processing Letters 118 (2017), 117-122
Deterministic versus randomized adaptive test cover PDF
Theoretical Computer Science 653 (2016), 42-52
preliminary version in:
9th International Conference on Algorithms and Complexity CIAC 2015, Paris, LNCS 9079, 182-193
Computing giant graph diameters PDF
27th International Workshop on Combinatorial Algorithms IWOCA 2016, Helsinki, LNCS 9843, 373-384
Adaptive group testing with a constrained number of positive responses improved PDF
Discrete Applied Mathematics 205 (2016), 208-212
Sufficient conditions for edit-optimal clusters PDF
Information Processing Letters 116 (2016), 267-272
preliminary short version in:
24th International Workshop on Combinatorial Algorithms IWOCA 2013, Rouen (France), LNCS 8288, 433-437
Summarizing online user reviews using bicliques PDF
with Azam Sheikh Muhammad and Olof Mogren
42nd International Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2016, Harrachov (Czech Republic), LNCS 9587, 569-579
Pairs covered by a sequence of sets PDF
20th International Symposium on Fundamentals of Computation Theory FCT 2015, Gdansk, LNCS 9210, 214-226
Finding and enumerating large intersections PDF
Theoretical Computer Science 580 (2015), 75-82
Parameterizations of hitting set of bundles and inverse scope PDF
Journal of Combinatorial Optimization 29 (2015), 847-855
The original publication is available at www.springerlink.com.
Strict group testing and the set basis problem PDF
with Azam Sheikh Muhammad and Gabor Wiener
Journal of Combinatorial Theory, Series A 126 (2014), 70-91
preliminary version of parts of the paper (by the first two authors) in:
19th International Computing and Combinatorics Conference COCOON 2013, Hangzhou, LNCS 7936, 446-457
Enumerating maximal bicliques in bipartite graphs with favorable degree sequences PDF
Information Processing Letters 114 (2014), 317-321
Editing simple graphs PDF
with Olof Mogren
Journal of Graph Algorithms and Applications 18 (2014), 557-576
preliminary version in:
8th International Workshop on Algorithms and Computation WALCOM 2014, IIT Madras, Chennai, LNCS 8344, 249-260
Two new perspectives on multi-stage group testing PDF
with Azam Sheikh Muhammad and Eberhard Triesch
Algorithmica 67 (2013), 324-354
The original publication is available at http://link.springer.com.
Fixed-parameter tractability of error correction in graphical linear systems PDF
with Omer Egecioglu and Leonid Molokov
7th International Workshop on Algorithms and Computation WALCOM 2013, IIT Kharagpur (India), LNCS 7748, 245-256
Error propagation in sparse linear systems with peptide-protein incidence matrices PDF
with Leonid Molokov
8th International Symposium on Bioinformatics Research and Applications ISBRA 2012, Dallas, LNCS (subseries LNBI) 7292, 72-83
A note on the parameterized complexity of unordered maximum tree orientation PDF
with Sebastian Böcker
Discrete Applied Mathematics 160 (2012), 1634-1638
Randomized group testing both query-optimal and minimal adaptive PDF
with Azam Sheikh Muhammad
*Best Paper Award* at the 38th International Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2012, Spindleruv Mlyn (Czech Republic), LNCS 7147, 214-225
Sparse solutions of sparse linear systems: Fixed-parameter tractability and an application of complex group testing PDF
Theoretical Computer Science 511 (2013), 137-146
preliminary version in:
6th International Symposium on Parameterized and Exact Computation IPEC 2011 (part of ALGO 2011), Saarbrucken, LNCS 7112, 94-105
Even faster parameterized cluster deletion and cluster editing PDF
with Sebastian Böcker
Information Processing Letters 111 (2011), 717-721
(For a correction and improvement see: D. Tsur: Cluster deletion revisited, arXiv:1907.08399v1, 2019)
Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover PDF
with Leonid Molokov
Theoretical Computer Science 452 (2012), 39-46
preliminary version in:
12th Algorithms and Data Structures Symposium WADS 2011, New York, LNCS 6844, 279-289
Bounds for nonadaptive group tests to estimate the amount of defectives PDF
with Azam Sheikh Muhammad
Discrete Mathematics, Algorithms and Applications 3 (2011), 517-536
Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries (ask for a copy)
Networks 57 (2011), 344-350
Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover PDF
Discrete Optimization 8 (2011), 18-24
Bounded-degree techniques accelerate some parameterized graph algorithms PDF
4th International Workshop on Parameterized and Exact Computation IWPEC 2009 (part of ALGO 2009), Copenhagen, LNCS 5917, 98-109
Pareto complexity of two-parameter FPT problems: A case study for partial vertex cover PDF
4th International Workshop on Parameterized and Exact Computation IWPEC 2009 (part of ALGO 2009), Copenhagen, LNCS 5917, 110-121
Competitive group testing and learning hidden vertex covers with minimum adaptivity PDF
with Azam Sheikh Muhammad
Discrete Mathematics, Algorithms and Applications 2 (2010), 291-311
Minimum common string partition parameterized PDF
8th Workshop on Algorithms in Bioinformatics WABI 2008, Karlsruhe, LNCS (subseries LNBI) 5251, 87-98
Fixed-parameter enumerability of cluster editing and related problems PDF
Theory of Computing Systems 46 (2010), 261-283
The original publication is available at www.springerlink.com.
Competitive search for longest empty intervals PDF (long version)
20th Canadian Conference on Computational Geometry CCCG 2008, Montreal
Multiple hypernode hitting sets and smallest two-cores with targets PDF
Journal of Combinatorial Optimization 18 (2009), 294-306
The original publication is available at www.springerlink.com.
Online search with time-varying price bounds
with Phuong Hoai Ha and Philippas Tsigas
Algorithmica 55 (2009), 619-642
The original publication is available at www.springerlink.com.
Homogeneous string segmentation using trees and weighted independent sets PDF
Algorithmica 57 (2010), 621-640
The union of minimal hitting sets: Parameterized combinatorial bounds and counting PDF
with Leonid Molokov
Journal of Discrete Algorithms 7 (2009), 391-401
A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs PDF
Information Processing Letters 100 (2006), 64-68
Fast algorithms for finding disjoint subsequences with extremal densities PS
with Anders Bergkvist
Pattern Recognition 39 (2006), 2281-2292, Special Issue on Bioinformatics.
Threshold group testing PDF
in: General Theory of Information Transfer and Combinatorics, LNCS 4123, 707-718
Overlaps help: Improved bounds for group testing with interval queries
with Ferdinando Cicalese, Libertad Tansini, and Sören Werth
Discrete Applied Mathematics 155 (2007), 288-299
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
Theoretical Computer Science 351 (2006), 337-350, Special Issue IWPEC 2004.

Disclaimer

This is a personal www page. Opinions expressed here do not represent the official views of Chalmers University of Technology. The author is not responsible for the contents of external links.