Organizatorzy

dr hab. Michał Pilipczuk, prof. ucz.

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

4 kwietnia 2025 14:15
Florian Hörsch (CISPA)
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and a demand graph H on a set T ⊆ V (G) of terminals, the task is …
21 marca 2025 14:15
Marta Piecyk
Graph homomorphism problem parameterized by cutwidth
For a fixed (target) graph H, in the graph homomorphism problem, denoted by Hom(H), we are given a graph G, and we have to determine whether there exists an edge preserving mapping f: V(G)-> V(H). …
14 marca 2025 14:15
Michał Pilipczuk
Erdős-Pósa property of tripods in directed graphs
A tripod in a directed graph D with sources S and sinks T is a subgraph consisting of the union of two S-T-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart …
28 lutego 2025 14:15
Marek Sokołowski (Max Planck Institute for Informatics)
Fully dynamic biconnectivity in Õ(log² n) time
We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph, i.e., the vertices whose removal would disconnect the graph. Our data structure supports insertion and deletion of edges, as …
17 stycznia 2025 14:15
Rose McCarty
Separators in sphere intersection graphs
We discuss the sphere dimension of graphs. This is the smallest integer d such that the graph can be represented as the intersection graph of a collection of spheres in R^d. We show that graphs …
6 grudnia 2024 14:00
Szymon Toruńczyk
Merge-width and First-Order Model Checking
We introduce merge-width, a family of graph parameters that unifies several structural graph measures, including treewidth, degeneracy, twin-width, clique-width, and generalized coloring numbers. Graph classes of bounded merge-width – for which the radius-r merge-width parameter …
29 listopada 2024 14:15
Marcin Pilipczuk
Bounding ε-scatter dimension via metric sparsity
A recent work of Abbasi et al. [FOCS 2023] introduced the notion of ε-scatter dimension of a metric space and showed a general framework for efficient parameterized approximation schemes (so-called EPASes) for a wide range …
22 listopada 2024 14:15
Kunal Dutta
A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels
Computing persistent homology of large datasets using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, compared to other typical …
15 listopada 2024 14:15
Wiktor Zuba
Space-Efficient Indexes for Uncertain Strings
Strings in the real world are often encoded with some level of uncertainty, for example, due to: unreliable data measurements; flexible sequence modeling; or noise introduced for privacy protection. In the character-level uncertainty model, an …
8 listopada 2024 14:15
Anita Dürr (Max Planck Institute for Informatics)
Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time ˜O(n + t√pmax), where n is the number of items, t is the knapsack capacity, and pmax is the maximum item profit. …
25 października 2024 14:15
Maël Dumas
On graphs coverable by k shortest paths
We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a single exponential function of k. As …
18 października 2024 14:15
Konrad Majewski
Parameterized Dynamic Data Structure for Split Completion
We design a randomized data structure that, for a fully dynamic graph G updated by edge insertions and deletions and integers k, d fixed upon initialization, maintains the answer to the Split Completion problem: whether …
29 kwietnia 2021 12:15
Jana Cslovjecsek (EPFL)
Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time
We consider n-fold integer programming problems and their generalizations. These are integer linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent sub-problems after deleting a small number …
15 kwietnia 2021 12:15
Tomáš Masařík (Simon Fraser University)
Flexible List Colorings in Graphs with Special Degeneracy Conditions
For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is …
1 kwietnia 2021 12:15
Michał Pilipczuk
Reducing randomness in Isolation Lemma on decomposable graphs
The classic Isolation Lemma of Mulmuley et al. states that if F is a non-empty family of subsets of a universe U of size n, and we draw a weight function f : U -> …