Barış Can Esmer,Ariel Kulik,Dániel Marx et al.
Barış Can Esmer et al.
In this paper, we consider a general notion of convolution. Let D be a finite domain and let Dn be the set of n-length vectors (tuples) of D. Let f:D×D→D be a function and let ⊕f be a coordinate-wise application of f. The f...
Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number [0.03%]
关于有界独立数有向图上的图布局问题的次指数时间参数算法
Pranabendu Misra,Saket Saurabh,Roohani Sharma et al.
Pranabendu Misra et al.
Fradkin and Seymour (J Comb Theory Ser B 110:19-46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is...
Sebastian Forster,Tijn de Vos
Sebastian Forster
A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of ( 1 ± ϵ ) . This paper considers computing cut sparsifiers of weighted graphs of size O ( n ...
Stephan Dominique Andres,François Dross,Melissa A Huggan et al.
Stephan Dominique Andres et al.
We consider two variants of orthogonal colouring games on graphs. In these games, two players alternate colouring uncoloured vertices (from a choice of m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and...
Stefan Lendl,Gerhard Woeginger,Lasse Wulf
Stefan Lendl
An instance of the non-preemptive tree packing problem consists of an undirected graph G = ( V , E ) together with a weight w(e) for every edge e ∈ E . The goal is to activate every edge e for some time interval of length w(e), such...
A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes [0.03%]
高阶Delaunay镶嵌和Alpha形状的一个简单算法
Herbert Edelsbrunner,Georg Osang
Herbert Edelsbrunner
We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-k mosaic from incrementally constructed lower-order mosaics a...
Tobias Friedrich,Hans Gawendowicz,Pascal Lenzner et al.
Tobias Friedrich et al.
During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network...
Bruno Pasqualotto Cavalar,Mrinal Kumar,Benjamin Rossman
Bruno Pasqualotto Cavalar
Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256-279, 2014), DNF sparsification Gopalan et al. (Comput. Complex. 22:275-310 2013), rando...
Selected Papers of the 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021 [0.03%]
第32届组合算法国际研讨会（IWOCA 2021）精选论文
Paola Flocchini,Lucia Moura
Paola Flocchini
Alejandro Grez,Filip Mazowiecki,Michał Pilipczuk et al.
Alejandro Grez et al.
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assu...