Antigen
发表于 2025-3-26 22:40:08
http://reply.papertrans.cn/24/2339/233824/233824_31.png
大方一点
发表于 2025-3-27 01:34:14
https://doi.org/10.1007/978-1-4615-2952-1can be solved in linear time on block graphs. For general graphs the best known algorithm runs in time .. For trees and interval graphs, linear-time algorithms are known. As block graphs form a superclass of trees, our result extends the classes of graphs on which this problem is solvable in linear time.
N防腐剂
发表于 2025-3-27 07:44:11
http://reply.papertrans.cn/24/2339/233824/233824_33.png
Mortal
发表于 2025-3-27 10:59:26
Broadcast Domination on Block Graphs in Linear Timecan be solved in linear time on block graphs. For general graphs the best known algorithm runs in time .. For trees and interval graphs, linear-time algorithms are known. As block graphs form a superclass of trees, our result extends the classes of graphs on which this problem is solvable in linear time.
单片眼镜
发表于 2025-3-27 14:45:56
Descriptional Complexity of Operations on Alternating and Boolean Automataerations on languages represented by boolean and alternating finite automata. We get tight bounds for intersection and union, and for concatenation and reversal of languages represented by boolean automata. In the case of star, and of concatenation and reversal of AFA languages, our upper and lower bounds differ by one.
没有准备
发表于 2025-3-27 19:26:51
Checking Tests for Read-Once Functions over Arbitrary Basesriables of . and . is the largest arity of functions in .. For some functions, this bound cannot be improved by more than a constant factor. The employed technique involves reconstructing . from its .-variable projections and provides a stronger form of Kuznetsov’s classic theorem on read-once representations.
STENT
发表于 2025-3-28 00:47:07
http://reply.papertrans.cn/24/2339/233824/233824_37.png
JEER
发表于 2025-3-28 03:06:01
Satisfiability Thresholds beyond , −XORSATver a domain of 4 elements with . = 3 arguments..The proof is based on variance calculations, using a technique introduced by Dubois/Mandler. However, several additional observations (of independent interest) are necessary.
inferno
发表于 2025-3-28 08:41:04
http://reply.papertrans.cn/24/2339/233824/233824_39.png
Dictation
发表于 2025-3-28 13:15:42
https://doi.org/10.1007/978-3-662-13150-3ntennae)..2) We present novel upper bound techniques which, in combination with stronger lower bounds, allow us to improve the previous approximation results for the edge length needed to achieve strong connectivity for . = 4 (from 2sin(./5) to optimal) and . = 3 (from . to .).