壮丽的去
发表于 2025-3-30 08:50:45
Optimizing Conjunctive Queries over Trees Using Schema Informationquery containment and validity are 2EXPTIME-complete w.r.t. a schema (DTD or Relax NG). Furthermore, we show that satisfiability for conjunctive queries w.r.t. a schema can be decided in NP. The problem is NP-hard already for queries using only one kind of axis. Finally, we consider conjunctive quer
漂泊
发表于 2025-3-30 14:36:14
Clustering with Partial Information, such that the editing cost is minimized. The . problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed parame
Gullible
发表于 2025-3-30 17:10:32
http://reply.papertrans.cn/63/6262/626142/626142_53.png
Processes
发表于 2025-3-30 23:00:35
On the Shortest Linear Straight-Line Program for Computing Linear Formsof linear forms. SLP is shown to be NP-hard. Furthermore, a special case of the corresponding decision problem is shown to be . SNP-Complete..Algorithms producing cancellation-free straight-line programs, those in which there is never any cancellation of variables in GF(2), have been proposed for ci
声音刺耳
发表于 2025-3-31 03:59:48
Flip Algorithm for Segment Triangulationstes, edges, and faces. The set of faces is a maximal set of disjoint triangles such that the vertices of each triangle are on three distinct sites. The segment Delaunay triangulation of . is the segment triangulation of . whose faces are inscribable in circles whose interiors do not intersect .. It
Lignans
发表于 2025-3-31 05:32:39
http://reply.papertrans.cn/63/6262/626142/626142_56.png
neuron
发表于 2025-3-31 11:05:14
A 6/5-Approximation Algorithm for the Maximum 3-Cover Problemcollection of at most . sets whose union contains the maximum number of elements from the ground set. This is a fundamental combinatorial optimization problem with applications to resource allocation. We study the simplest APX-hard variant of the problem where all sets are of size at most 3 and we p
intelligible
发表于 2025-3-31 17:09:41
http://reply.papertrans.cn/63/6262/626142/626142_58.png
发生
发表于 2025-3-31 17:56:00
http://reply.papertrans.cn/63/6262/626142/626142_59.png
Impugn
发表于 2025-4-1 00:30:05
A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems} without two consecutive 1. Given a set . of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not . is a finite union of arithmetic progressions. We obtain a decision procedure under some