流逝
发表于 2025-3-25 06:36:26
https://doi.org/10.1007/978-88-470-0513-6owing properties. There exists a constant . such that the degree of the .-th vertex is at least .(.) and at most ., and it is impossible to make all degrees equal to .(.) by removing the graph’s edges. Moreover, any proof of this statement in the resolution proof system has size .. This result impli
哑剧
发表于 2025-3-25 09:42:17
http://reply.papertrans.cn/24/2338/233755/233755_22.png
configuration
发表于 2025-3-25 13:16:46
http://reply.papertrans.cn/24/2338/233755/233755_23.png
合唱团
发表于 2025-3-25 18:59:57
On Growth and Fluctuation of ,-Abelian Complexity,ticular aspects of this extension: First, how much the complexity can increase when moving from a level . to the next one. Second, how much the complexity of a given word can fluctuate. For both questions we give optimal solutions.
同时发生
发表于 2025-3-25 23:46:31
A Polynomial-Time Algorithm for Outerplanar Diameter Improvement,s diameter at most .. We provide a dynamic programming algorithm that solves this problem in polynomial time. . demonstrates several structural analogues to the celebrated and challenging . problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.
真繁荣
发表于 2025-3-26 02:29:51
Conference proceedings 2015015..The 25 full papers presented in this volume were carefully reviewed and selected from 61 submissions. In addition the book contains 4 invited lectures. The scope of the proposed topics is quite broad and covers a wide range of areas in theoretical computer science and its applications..
Harness
发表于 2025-3-26 04:28:01
https://doi.org/10.1007/978-3-319-20297-6Approximation algorithms; Computational complexity; Discrete mathematics; Formal grammars; Graph algorit
缓和
发表于 2025-3-26 11:10:03
978-3-319-20296-9Springer International Publishing Switzerland 2015
没花的是打扰
发表于 2025-3-26 12:51:29
http://reply.papertrans.cn/24/2338/233755/233755_29.png
拱形面包
发表于 2025-3-26 19:41:54
Propositional Proofs in Frege and Extended Frege Systems (Abstract),We discuss recent results on the propositional proof complexity of Frege proof systems, including some recently discovered quasipolynomial size proofs for the pigeonhole principle and the Kneser-Lovász theorem. These are closely related to formalizability in bounded arithmetic.