Flustered
发表于 2025-3-23 13:36:19
Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing,linear equations (i.e., where the rows of . are .-sparse) is fixed-parameter tractable (FPT) in the combined parameter .,.. For . = 2 the problem is simple. For 0,1-matrices . we can also compute an .(..) kernel. For systems of linear inequalities we get an FPT result in the combined parameter .,.,
INCH
发表于 2025-3-23 14:12:00
New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree,due to Williams) solving them in less than 2. steps uses exponential space. Scott and Sorkin give an algorithm with . time and polynomial space for these problems, where . is the average variable degree. We improve this bound to . for MAX-2-SAT and . for MAX-2-CSP. We also prove stronger upper bound
Flu表流动
发表于 2025-3-23 22:04:27
Improved Parameterized Algorithms for above Average Constraint Satisfaction,e, a simple random assignment for . allows 7/8-approximation and for every . > 0 there is no polynomial-time (7/8 + .)-approximation unless P=NP. Another example is the . of bounded arity. Given the expected fraction . of the constraints satisfied by a random assignment (i.e. permutation), there is
Accede
发表于 2025-3-23 22:13:53
http://reply.papertrans.cn/75/7412/741156/741156_14.png
Apoptosis
发表于 2025-3-24 03:25:01
Kernel Bounds for Path and Cycle Problems, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a mod
打折
发表于 2025-3-24 09:04:34
http://reply.papertrans.cn/75/7412/741156/741156_16.png
裙带关系
发表于 2025-3-24 11:09:12
http://reply.papertrans.cn/75/7412/741156/741156_17.png
繁荣地区
发表于 2025-3-24 17:16:08
Simpler Linear-Time Kernelization for Planar Dominating Set,domination number of ., i.e., the size of a smallest dominating set in .. In the language of parameterized computation, the new algorithm is a linear-time kernelization for the NP-complete . problem that produces a kernel of linear size. Such an algorithm was previously known (van Bevern et al., the
MURAL
发表于 2025-3-24 20:20:09
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs,(.)) with .(.) = .(.′). In addition, a minimum dominating set for . can be inferred from a minimum dominating set for .′. In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard . problem on planar graphs, where the kernelization takes linear time. This impr
AUGER
发表于 2025-3-25 03:03:01
http://reply.papertrans.cn/75/7412/741156/741156_20.png