143 Search Results for "F�rnkranz, Johannes"

Document
DOI: 10.4230/DagRep.13.10.182
Approaches and Applications of Inductive Programming (Dagstuhl Seminar 23442)

Authors: Luc De Raedt, Ute Schmid, and Johannes Langer

Published in: Dagstuhl Reports, Volume 13, Issue 10 (2024)

Abstract
The Dagstuhl Seminar "Approaches and Applications of Inductive Programming" (AAIP) has taken place for the sixth time. The Dagstuhl Seminar series brings together researchers concerned with learning programs from input/output examples from different areas, mostly from machine learning and other branches of artificial intelligence research, cognitive scientists interested in human learning in complex domains, and researchers with a background in formal methods and programming languages. Main topics adressed in the AAIP 2023 seminar have been neurosymbolic approaches to IP bringing together learning and reasoning, IP as a post-hoc approach to explaining decision-making of deep learning blackbox models, and exploring the potential of deep learning approaches, especially large language models such as OpenAI Codex for IP. Topics discussed in working groups were Large Language Models and inductive programming in cognitive architectures, avoiding too much search in inductive programming, finding suitable benchmark problems, and evaluation criteria for interpretability and explainability of inductive programming.
Cite as

Luc De Raedt, Ute Schmid, and Johannes Langer. Approaches and Applications of Inductive Programming (Dagstuhl Seminar 23442). In Dagstuhl Reports, Volume 13, Issue 10, pp. 182-211, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{deraedt_et_al:DagRep.13.10.182,
  author =	{De Raedt, Luc and Schmid, Ute and Langer, Johannes},
  title =	{{Approaches and Applications of Inductive Programming (Dagstuhl Seminar 23442)}},
  pages =	{182--211},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{10},
  editor =	{De Raedt, Luc and Schmid, Ute and Langer, Johannes},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.10.182},
  URN =		{urn:nbn:de:0030-drops-198397},
  doi =		{10.4230/DagRep.13.10.182},
  annote =	{Keywords: explainable ai, human-like machine learning, inductive logic programming, interpretable machine learning, neuro-symbolic ai}
}
Document
DOI: 10.4230/DagRep.13.9.116
Human-Centered Approaches for Provenance in Automated Data Science (Dagstuhl Seminar 23372)

Authors: Anamaria Crisan, Lars Kotthoff, Marc Streit, and Kai Xu

Published in: Dagstuhl Reports, Volume 13, Issue 9 (2024)

Abstract
The scope of automated machine learning (AutoML) technology has extended beyond its initial boundaries of model selection and hyperparameter tuning and towards end-to-end development and refinement of data science pipelines. These advances, both theoretical and realized, make the tools of data science more readily available to domain experts that rely on low- or no-code tooling options to analyze and make sense of their data. To ensure that automated data science technologies are applied both effectively and responsibly, it becomes increasingly urgent to carefully audit the decisions made both automatically and with guidance from humans. This Dagstuhl Seminar examines human-centered approaches for provenance in automated data science. While prior research concerning provenance and machine learning exists, it does not address the expanded scope of automated approaches and the consequences of applying such techniques at scale to the population of domain experts. In addition, most of the previous works focus on the automated part of this process, leaving a gap on the support for the sensemaking tasks users need to perform, such as selecting the datasets and candidate models and identifying potential causes for poor performance. The seminar brought together experts from across provenance, information visualization, visual analytics, machine learning, and human-computer interaction to articulate the user challenges posed by AutoML and automated data science, discuss the current state of the art, and propose directions for new research. More specifically, this seminar: - articulates the state of the art in AutoML and automated data science for supporting the provenance of decision making, - describes the challenges that data scientists and domain experts face when interfacing with automated approaches to make sense of an automated decision, - examines the interface between data-centric, model-centric, and user-centric models of provenance and how they interact with automated techniques, and - encourages exploration of human-centered approaches; for example leveraging visualization.
Cite as

Anamaria Crisan, Lars Kotthoff, Marc Streit, and Kai Xu. Human-Centered Approaches for Provenance in Automated Data Science (Dagstuhl Seminar 23372). In Dagstuhl Reports, Volume 13, Issue 9, pp. 116-136, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{crisan_et_al:DagRep.13.9.116,
  author =	{Crisan, Anamaria and Kotthoff, Lars and Streit, Marc and Xu, Kai},
  title =	{{Human-Centered Approaches for Provenance in Automated Data Science (Dagstuhl Seminar 23372)}},
  pages =	{116--136},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{9},
  editor =	{Crisan, Anamaria and Kotthoff, Lars and Streit, Marc and Xu, Kai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.9.116},
  URN =		{urn:nbn:de:0030-drops-198236},
  doi =		{10.4230/DagRep.13.9.116},
  annote =	{Keywords: Dagstuhl Seminar, Provenance, AutoML, Data Science, Information Visualisation, Visual Analytics, Machine Learning, Human-Computer Interaction}
}
Document
DOI: 10.4230/DagRep.13.8.1
Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)

Authors: George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman

Published in: Dagstuhl Reports, Volume 13, Issue 8 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23331 "Recent Trends in Graph Decomposition", which took place from 13. August to 18. August, 2023. The seminar brought together 33 experts from academia and industry to discuss graph decomposition, a pivotal technique for handling massive graphs in applications such as social networks and scientific simulations. The seminar addressed the challenges posed by contemporary hardware designs, the potential of deep neural networks and reinforcement learning in developing heuristics, the unique optimization requirements of large sparse data, and the need for scalable algorithms suitable for emerging architectures. Through presentations, discussions, and collaborative sessions, the event fostered an exchange of innovative ideas, leading to the creation of community notes highlighting key open problems in the field.
Cite as

George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman. Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331). In Dagstuhl Reports, Volume 13, Issue 8, pp. 1-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{karypis_et_al:DagRep.13.8.1,
  author =	{Karypis, George and Schulz, Christian and Strash, Darren and Ajwani, Deepak and Bisseling, Rob H. and Casel, Katrin and \c{C}ataly\"{u}rek, \"{U}mit V. and Chevalier, C\'{e}dric and Chudigiewitsch, Florian and Faraj, Marcelo Fonseca and Fellows, Michael and Gottesb\"{u}ren, Lars and Heuer, Tobias and Kaya, Kamer and Lacki, Jakub and Langguth, Johannes and Li, Xiaoye Sherry and Mayer, Ruben and Meintrup, Johannes and Mizutani, Yosuke and Pellegrini, Fran\c{c}ois and Petrini, Fabrizio and Rosamond, Frances and Safro, Ilya and Schlag, Sebastian and Sharma, Roohani and Sullivan, Blair D. and U\c{c}ar, Bora and Yzelman, Albert-Jan},
  title =	{{Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)}},
  pages =	{1--45},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{8},
  editor =	{Karypis, George and Schulz, Christian and Strash, Darren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.8.1},
  URN =		{urn:nbn:de:0030-drops-198114},
  doi =		{10.4230/DagRep.13.8.1},
  annote =	{Keywords: combinatorial optimization, experimental algorithmics, parallel algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.6
On a Hierarchy of Spectral Invariants for Graphs

Authors: V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard basis vectors and their projections onto eigenspaces of the adjacency matrix. We provide a purely combinatorial characterization of this hierarchy in terms of the walk counts. This allows us to give a complete answer to Fürer’s question about the strength of his invariants in distinguishing non-isomorphic graphs in comparison to the 2-dimensional Weisfeiler-Leman algorithm, extending the recent work of Rattan and Seppelt (SODA 2023). As another application of the characterization, we prove that almost all graphs are determined up to isomorphism in terms of the spectrum and the angles, which is of interest in view of the long-standing open problem whether almost all graphs are determined by their eigenvalues alone. Finally, we describe the exact relationship between the hierarchy and the Weisfeiler-Leman algorithms for small dimensions, as also some other important spectral characteristics of a graph such as the generalized and the main spectra.
Cite as

V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On a Hierarchy of Spectral Invariants for Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.STACS.2024.6,
  author =	{Arvind, V. and Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Verbitsky, Oleg},
  title =	{{On a Hierarchy of Spectral Invariants for Graphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.6},
  URN =		{urn:nbn:de:0030-drops-197166},
  doi =		{10.4230/LIPIcs.STACS.2024.6},
  annote =	{Keywords: Graph Isomorphism, spectra of graphs, combinatorial refinement, strongly regular graphs}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.11
How Does Knowledge Evolve in Open Knowledge Graphs?

Authors: Axel Polleres, Romana Pernisch, Angela Bonifati, Daniele Dell'Aglio, Daniil Dobriy, Stefania Dumbrava, Lorena Etcheverry, Nicolas Ferranti, Katja Hose, Ernesto Jiménez-Ruiz, Matteo Lissandrini, Ansgar Scherp, Riccardo Tommasini, and Johannes Wachs

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Openly available, collaboratively edited Knowledge Graphs (KGs) are key platforms for the collective management of evolving knowledge. The present work aims t o provide an analysis of the obstacles related to investigating and processing specifically this central aspect of evolution in KGs. To this end, we discuss (i) the dimensions of evolution in KGs, (ii) the observability of evolution in existing, open, collaboratively constructed Knowledge Graphs over time, and (iii) possible metrics to analyse this evolution. We provide an overview of relevant state-of-the-art research, ranging from metrics developed for Knowledge Graphs specifically to potential methods from related fields such as network science. Additionally, we discuss technical approaches - and their current limitations - related to storing, analysing and processing large and evolving KGs in terms of handling typical KG downstream tasks.
Cite as

Axel Polleres, Romana Pernisch, Angela Bonifati, Daniele Dell'Aglio, Daniil Dobriy, Stefania Dumbrava, Lorena Etcheverry, Nicolas Ferranti, Katja Hose, Ernesto Jiménez-Ruiz, Matteo Lissandrini, Ansgar Scherp, Riccardo Tommasini, and Johannes Wachs. How Does Knowledge Evolve in Open Knowledge Graphs?. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 11:1-11:59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{polleres_et_al:TGDK.1.1.11,
  author =	{Polleres, Axel and Pernisch, Romana and Bonifati, Angela and Dell'Aglio, Daniele and Dobriy, Daniil and Dumbrava, Stefania and Etcheverry, Lorena and Ferranti, Nicolas and Hose, Katja and Jim\'{e}nez-Ruiz, Ernesto and Lissandrini, Matteo and Scherp, Ansgar and Tommasini, Riccardo and Wachs, Johannes},
  title =	{{How Does Knowledge Evolve in Open Knowledge Graphs?}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{11:1--11:59},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.11},
  URN =		{urn:nbn:de:0030-drops-194855},
  doi =		{10.4230/TGDK.1.1.11},
  annote =	{Keywords: KG evolution, temporal KG, versioned KG, dynamic KG}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2023.37
PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)

Authors: Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
Twin-width (tww) is a parameter measuring the similarity of an undirected graph to a co-graph [Édouard Bonnet et al., 2022]. It is useful to analyze the parameterized complexity of various graph problems. This paper presents two algorithms to compute the twin-width and to provide a contraction sequence as witness. The two algorithms are motivated by the PACE 2023 challenge, one for the exact track and one for the heuristic track. Each algorithm produces a contraction sequence witnessing (i) the minimal twin-width admissible by the graph in the exact track (ii) an upper bound on the twin-width as tight as possible in the heuristic track. Our heuristic algorithm relies on several greedy approaches with different performance characteristics to find and improve solutions. For large graphs we use locality sensitive hashing to approximately identify suitable contraction candidates. The exact solver follows a branch-and-bound design. It relies on the heuristic algorithm to provide initial upper bounds, and uses lower bounds via contraction sequences to show the optimality of a heuristic solution found in some branch.
Cite as

Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck. PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM). In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 37:1-37:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{leonhardt_et_al:LIPIcs.IPEC.2023.37,
  author =	{Leonhardt, Alexander and Dell, Holger and Haak, Anselm and Kammer, Frank and Meintrup, Johannes and Meyer, Ulrich and Penschuck, Manuel},
  title =	{{PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{37:1--37:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.37},
  URN =		{urn:nbn:de:0030-drops-194563},
  doi =		{10.4230/LIPIcs.IPEC.2023.37},
  annote =	{Keywords: PACE 2023 Challenge, Heuristic, Exact, Twin-Width}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.36
Coloring and Recognizing Mixed Interval Graphs

Authors: Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
A mixed interval graph is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph G, an interval u receives a lower (different) color than an interval v if G contains arc (u,v) (edge {u,v}). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. For coloring general mixed interval graphs, we present a min {ω(G), λ(G)+1}-approximation algorithm, where ω(G) is the size of a largest clique and λ(G) is the length of a longest directed path in G. For the subclass of bidirectional interval graphs (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs. We introduce a new natural class of mixed interval graphs, which we call containment interval graphs. In such a graph, there is an arc (u,v) if interval u contains interval v, and there is an edge {u,v} if u and v overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring.
Cite as

Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. Coloring and Recognizing Mixed Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gutowski_et_al:LIPIcs.ISAAC.2023.36,
  author =	{Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Klesen, Felix and Rz\k{a}\.{z}ewski, Pawe{\l} and Wolff, Alexander and Zink, Johannes},
  title =	{{Coloring and Recognizing Mixed Interval Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.36},
  URN =		{urn:nbn:de:0030-drops-193388},
  doi =		{10.4230/LIPIcs.ISAAC.2023.36},
  annote =	{Keywords: Interval Graphs, Mixed Graphs, Graph Coloring}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.44
Succinct Planar Encoding with Minor Operations

Authors: Frank Kammer and Johannes Meintrup

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Let G be an unlabeled planar and simple n-vertex graph. Unlabeled graphs are graphs where the label-information is either not given or lost during the construction of data-structures. We present a succinct encoding of G that provides induced-minor operations, i.e., edge contractions and vertex deletions. Any sequence of such operations is processed in O(n) time in the word-RAM model. At all times the encoding provides constant time (per element output) neighborhood access and degree queries. Optional hash tables extend the encoding with constant expected time adjacency queries and edge-deletion (thus, all minor operations are supported) such that any number of edge deletions are computed in O(n) expected time. Constructing the encoding requires O(n) bits and O(n) time. The encoding requires ℋ(n) + o(n) bits of space with ℋ(n) being the entropy of encoding a planar graph with n vertices. Our data structure is based on the recent result of Holm et al. [ESA 2017] who presented a linear time contraction data structure that allows to maintain parallel edges and works for labeled graphs, but uses Θ(n log n) bits of space. We combine the techniques used by Holm et al. with novel ideas and the succinct encoding of Blelloch and Farzan [CPM 2010] for arbitrary separable graphs. Our result partially answers the question raised by Blelloch and Farzan whether their encoding can be modified to allow modifications of the graph.
Cite as

Frank Kammer and Johannes Meintrup. Succinct Planar Encoding with Minor Operations. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.ISAAC.2023.44,
  author =	{Kammer, Frank and Meintrup, Johannes},
  title =	{{Succinct Planar Encoding with Minor Operations}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.44},
  URN =		{urn:nbn:de:0030-drops-193460},
  doi =		{10.4230/LIPIcs.ISAAC.2023.44},
  annote =	{Keywords: planar graph, r-division, separator, succinct encoding, graph minors}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.62
An Evaluation of the Impact of Ignition Location Uncertainty on Forest Fire Ignition Prediction Using Bayesian Logistic Regression (Short Paper)

Authors: David Röbl, Rizwan Bulbul, Johannes Scholz, Mortimer M. Müller, and Harald Vacik

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
This study investigates the impact of location uncertainty on the predictive performance of Bayesian Logistic Regression (BLR) for forest fire ignition prediction in Austria. Historical forest fire ignitions are used to create a dataset for training models with the capability to assess the general forest fire ignition susceptibility. Each recorded fire ignition contains a timestamp, the estimated location of the ignition and a radius defining the area within which the unknown true location of the ignition point is located. As the values of the predictive features are calculated based on the assumed location, and not the unknown true location, the training data is biased due to input uncertainties. This study is set to assess the impact of input data uncertainty on the predictive performance of the model. For this we use a data binning approach that splits the input data into groups based on their location uncertainty and use them later for training multiple BLR models. The predictive performance of the models is then compared based on their accuracy, area under the receiver operating characteristic curve (AUC) scores and brier scores. The study revealed that higher location uncertainty leads to decreased accuracy and AUC score, accompanied by an increase in the brier score, while demonstrating that the BLR model trained on a smaller high-quality dataset outperforms the model trained on the full dataset, despite its smaller size. The study’s contribution is to provide insights into the practical implications of location uncertainty on the quality of forest fire susceptibility predictions, with potential implications for forest risk management and forest fire documentation.
Cite as

David Röbl, Rizwan Bulbul, Johannes Scholz, Mortimer M. Müller, and Harald Vacik. An Evaluation of the Impact of Ignition Location Uncertainty on Forest Fire Ignition Prediction Using Bayesian Logistic Regression (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 62:1-62:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{robl_et_al:LIPIcs.GIScience.2023.62,
  author =	{R\"{o}bl, David and Bulbul, Rizwan and Scholz, Johannes and M\"{u}ller, Mortimer M. and Vacik, Harald},
  title =	{{An Evaluation of the Impact of Ignition Location Uncertainty on Forest Fire Ignition Prediction Using Bayesian Logistic Regression}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{62:1--62:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.62},
  URN =		{urn:nbn:de:0030-drops-189576},
  doi =		{10.4230/LIPIcs.GIScience.2023.62},
  annote =	{Keywords: Forest Fire Prediction, Ignition Location Uncertainty, Bayesian Logistic Regression, Bayesian Inference, Probabilistic Programming}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.63
Calculating Shadows with U-Nets for Urban Environments (Short Paper)

Authors: Dominik Rothschedl, Franz Welscher, Franziska Hübl, Ivan Majic, Daniele Giannandrea, Matthias Wastian, Johannes Scholz, and Niki Popper

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Shadow calculation is an important prerequisite for many urban and environmental analyses such as the assessment of solar energy potential. We propose a neural net approach that can be trained with 3D geographical information and predict the presence and depth of shadows. We adapt a U-Net algorithm traditionally used in biomedical image segmentation and train it on sections of Styria, Austria. Our two-step approach first predicts binary existence of shadows and then estimates the depth of shadows as well. Our results on the case study of Styria, Austria show that the proposed approach can predict in both models shadows with over 80% accuracy which is satisfactory for real-world applications, but still leaves room for improvement.
Cite as

Dominik Rothschedl, Franz Welscher, Franziska Hübl, Ivan Majic, Daniele Giannandrea, Matthias Wastian, Johannes Scholz, and Niki Popper. Calculating Shadows with U-Nets for Urban Environments (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 63:1-63:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rothschedl_et_al:LIPIcs.GIScience.2023.63,
  author =	{Rothschedl, Dominik and Welscher, Franz and H\"{u}bl, Franziska and Majic, Ivan and Giannandrea, Daniele and Wastian, Matthias and Scholz, Johannes and Popper, Niki},
  title =	{{Calculating Shadows with U-Nets for Urban Environments}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{63:1--63:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.63},
  URN =		{urn:nbn:de:0030-drops-189581},
  doi =		{10.4230/LIPIcs.GIScience.2023.63},
  annote =	{Keywords: Neural Net, U-Net, Residual Net, Shadow Calculation}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.82
Harnessing the Sunlight on Facades - an Approach for Determining Vertical Photovoltaic Potential (Short Paper)

Authors: Franz Welscher, Ivan Majic, Franziska Hübl, Rizwan Bulbul, and Johannes Scholz

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
The paper deals with the calculation of the photovoltaic potential of vertical structures. Photovoltaic systems are a core technology for producing renewable energy. As roughly 50% of the population on planet Earth lives in urban environments, the production of renewable energy in urban contexts is of particular interest. As several papers have elaborated on the photovoltaic potential of roofs, this paper focuses on vertical structures. Hence, we present a methodology to extract facades suitable for photovoltaic installation, calculate their southness and percentage of shaded areas. The approach is successfully tested, based on a dataset located in the city of Graz, Styria (Austria). The results show the wall structures of each building, the respective shadow depth, and their score based on a multi-criteria analysis that represents the suitability for the installation of a photovoltaic system.
Cite as

Franz Welscher, Ivan Majic, Franziska Hübl, Rizwan Bulbul, and Johannes Scholz. Harnessing the Sunlight on Facades - an Approach for Determining Vertical Photovoltaic Potential (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 82:1-82:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{welscher_et_al:LIPIcs.GIScience.2023.82,
  author =	{Welscher, Franz and Majic, Ivan and H\"{u}bl, Franziska and Bulbul, Rizwan and Scholz, Johannes},
  title =	{{Harnessing the Sunlight on Facades - an Approach for Determining Vertical Photovoltaic Potential}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{82:1--82:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.82},
  URN =		{urn:nbn:de:0030-drops-189777},
  doi =		{10.4230/LIPIcs.GIScience.2023.82},
  annote =	{Keywords: Vertical Photovoltaics, Facades, Southness, Multi-Criteria-Analysis, Shadow}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.30
On Connectivity in Random Graph Models with Limited Dependencies

Authors: Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
For any positive edge density p, a random graph in the Erdős-Rényi G_{n,p} model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are independent while incident edges may be dependent and ask: what is the minimum probability ρ(n), such that for any distribution 𝒢 (in this model) on graphs with n vertices in which each potential edge has a marginal probability of being present at least ρ(n), a graph drawn from 𝒢 is connected with non-zero probability? As it turns out, the condition "edges that do not share endpoints are independent" needs to be clarified and the answer to the question above is sensitive to the specification. In fact, we formalize this intuitive description into a strict hierarchy of five independence conditions, which we show to have at least three different behaviors for the threshold ρ(n). For each condition, we provide upper and lower bounds for ρ(n). In the strongest condition, the coloring model (which includes, e.g., random geometric graphs), we show that ρ(n) → 2-ϕ ≈ 0.38 for n → ∞, proving a conjecture by Badakhshian, Falgas-Ravry, and Sharifzadeh. This separates the coloring models from the weaker independence conditions we consider, as there we prove that ρ(n) > 0.5-o(n). In stark contrast to the coloring model, for our weakest independence condition - pairwise independence of non-adjacent edges - we show that ρ(n) lies within O(1/n²) of the threshold 1-2/n for completely arbitrary distributions.
Cite as

Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl. On Connectivity in Random Graph Models with Limited Dependencies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lengler_et_al:LIPIcs.APPROX/RANDOM.2023.30,
  author =	{Lengler, Johannes and Martinsson, Anders and Petrova, Kalina and Schnider, Patrick and Steiner, Raphael and Weber, Simon and Welzl, Emo},
  title =	{{On Connectivity in Random Graph Models with Limited Dependencies}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{30:1--30:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.30},
  URN =		{urn:nbn:de:0030-drops-188556},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.30},
  annote =	{Keywords: Random Graphs, Independence, Dependency, Connectivity, Threshold, Probabilistic Method}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.66
On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Authors: Peter Mayr

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
For a fixed finite algebra 𝐀, we consider the decision problem SysTerm(𝐀): does a given system of term equations have a solution in 𝐀? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of 𝐀. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [Bulatov, 2017] and Zhuk [Zhuk, 2017], it follows that SysTerm(𝐀) for a finite algebra 𝐀 is in P if 𝐀 has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra 𝐀 in a congruence modular variety (e.g. for a quasigroup), SysTerm(𝐀) is in P if the core of 𝐀 is abelian and is NP-complete otherwise. Given 𝐀 by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.
Cite as

Peter Mayr. On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mayr:LIPIcs.MFCS.2023.66,
  author =	{Mayr, Peter},
  title =	{{On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.66},
  URN =		{urn:nbn:de:0030-drops-186007},
  doi =		{10.4230/LIPIcs.MFCS.2023.66},
  annote =	{Keywords: systems of equations, general algebras, constraint satisfaction}
}
Document
DOI: 10.4230/LIPIcs.SAT.2023.3
CadiBack: Extracting Backbones with CaDiCaL

Authors: Armin Biere, Nils Froleyks, and Wenxi Wang

Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)

Abstract
The backbone of a satisfiable formula is the set of literals that are true in all its satisfying assignments. Backbone computation can improve a wide range of SAT-based applications, such as verification, fault localization and product configuration. In this tool paper, we introduce a new backbone extraction tool called CadiBack. It takes advantage of unique features available in our state-of-the-art SAT solver CaDiCaL including transparent inprocessing and single clause assumptions, which have not been evaluated in this context before. In addition, CaDiCaL is enhanced with an improved algorithm to support model rotation by utilizing watched literal data structures. In our comprehensive experiments with a large number of benchmarks, CadiBack solves 60% more instances than the state-of-the-art backbone extraction tool MiniBones. Our tool is thoroughly tested with fuzzing, internal correctness checking and cross-checking on a large benchmark set. It is publicly available as open source, well documented and easy to extend.
Cite as

Armin Biere, Nils Froleyks, and Wenxi Wang. CadiBack: Extracting Backbones with CaDiCaL. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{biere_et_al:LIPIcs.SAT.2023.3,
  author =	{Biere, Armin and Froleyks, Nils and Wang, Wenxi},
  title =	{{CadiBack: Extracting Backbones with CaDiCaL}},
  booktitle =	{26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)},
  pages =	{3:1--3:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-286-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{271},
  editor =	{Mahajan, Meena and Slivovsky, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.3},
  URN =		{urn:nbn:de:0030-drops-184655},
  doi =		{10.4230/LIPIcs.SAT.2023.3},
  annote =	{Keywords: Satisfiability, Backbone, Incremental Solving}
}
Document
DOI: 10.4230/LIPIcs.SAT.2023.20
QMusExt: A Minimal (Un)satisfiable Core Extractor for Quantified Boolean Formulas

Authors: Andreas Plank and Martina Seidl

Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)

Abstract
In this paper, we present QMusExt, a tool for the extraction of minimal unsatisfiable sets (MUS) from quantified Boolean formulas (QBFs) in prenex conjunctive normal form (PCNF). Our tool generalizes an efficient algorithm for MUS extraction from propositional formulas that analyses and rewrites resolution proofs generated by SAT solvers. In addition to extracting unsatisfiable cores from false formulas in PCNF, we apply QMusExt also to obtain satisfiable cores from Q-resolution proofs of true formulas in prenex disjunctive normal form (PDNF).
Cite as

Andreas Plank and Martina Seidl. QMusExt: A Minimal (Un)satisfiable Core Extractor for Quantified Boolean Formulas. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 20:1-20:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{plank_et_al:LIPIcs.SAT.2023.20,
  author =	{Plank, Andreas and Seidl, Martina},
  title =	{{QMusExt: A Minimal (Un)satisfiable Core Extractor for Quantified Boolean Formulas}},
  booktitle =	{26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)},
  pages =	{20:1--20:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-286-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{271},
  editor =	{Mahajan, Meena and Slivovsky, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.20},
  URN =		{urn:nbn:de:0030-drops-184824},
  doi =		{10.4230/LIPIcs.SAT.2023.20},
  annote =	{Keywords: Minimal Unsatisfiable Core, Quantified Boolean Formula}
}
  • Refine by Author
  • 12 Fischer, Johannes
  • 7 Köbler, Johannes
  • 7 Lengler, Johannes
  • 6 Fichte, Johannes K.
  • 6 Hecher, Markus
  • Show More...

  • Refine by Classification
  • 10 Theory of computation → Problems, reductions and completeness
  • 8 Mathematics of computing → Graph algorithms
  • 8 Theory of computation → Design and analysis of algorithms
  • 7 Theory of computation → Parameterized complexity and exact algorithms
  • 6 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 7 parameterized complexity
  • 3 Cryptography
  • 3 anti-unification
  • 3 counting complexity
  • 3 parallel algorithms
  • Show More...

  • Refine by Type
  • 143 document

  • Refine by Publication Year
  • 21 2023
  • 17 2022
  • 15 2019
  • 15 2021
  • 13 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact