Daniel Funke,Demian Hespe,Peter Sanders et al.
Daniel Funke et al.
In bi-criteria optimization problems, the goal is typically to compute the set of Pareto-optimal solutions. Many algorithms for these types of problems rely on efficient merging or combining of partial solutions and filtering of dominated s...
Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound [0.03%]
多重图中参数化最大裁剪问题的线性时间算法（超过Poljak-Turzik界的解）
Jonas Lill,Kalina Petrova,Simon Weber
Jonas Lill
MaxCut is a classical NP -complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdös bound states that any connected graph on n vertices with m edges contains a cut of size at least m 2 + n - ...
Bodo Manthey,Jesse van Rhijn
Bodo Manthey
The 2-opt heuristic is a simple local search heuristic for the travelling salesperson problem (TSP). Although it usually performs well in practice, its worst-case running time is exponential in the number of cities. Attempts to reconcile th...
Counting Temporal Paths [0.03%]
计数时空路径
Jessica Enright,Kitty Meeks,Hendrik Molter
Jessica Enright
This work investigates the parameterised complexity of counting temporal paths. The problem of counting temporal paths is mainly motivated by temporal betweenness computation. The betweenness centrality of a vertex v is an important central...
Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs [0.03%]
Impagliazzo-Nisan-Wigderson型伪随机生成器对抗置换分支程序的限制
William M Hoza,Edward Pyne,Salil Vadhan
William M Hoza
The classic Impagliazzo-Nisan-Wigderson (INW) pseudorandom generator (PRG) (STOC '94) for space-bounded computation uses a seed of length O ( log n · log ( n w / ε ) + log d ) to fool ordered branching programs of length n, width...
Ameet Gadekar
Ameet Gadekar
The Set Packing problem is, given a collection of sets S over a ground set U, to find a maximum collection of sets that are pairwise disjoint. The problem is among the most fundamental NP-hard optimization problems that have been studied ex...
Kshitij Gajjar,Agastya Vibhuti Jha,Manish Kumar et al.
Kshitij Gajjar et al.
Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (...
Slim Tree-Cut Width [0.03%]
狭隘的树剖宽度
Robert Ganian,Viktoriia Korchemna
Robert Ganian
Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-...
Sergio Cabello,David Gajser
Sergio Cabello
For a set Q of points in the plane and a real number δ≥0, let Gδ(Q) be the graph defined on Q by connecting each pair of points at distance at most δ.We consider the connectivity of Gδ(Q) in the best scenario when ...
Oswin Aichholzer,Ruy Fabila-Monroy,Philipp Kindermann et al.
Oswin Aichholzer et al.
For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least Cn/2 different plane perfect matchings, where Cn/2 is the n/2-th...