We adopt the following symbols and notations. Let C;be the class of all real continuous functions in [0,1] which have N continuousderivatives, L;0,1];be the space of real pth power integrable functions on [0,1], and ...We adopt the following symbols and notations. Let C;be the class of all real continuous functions in [0,1] which have N continuousderivatives, L;0,1];be the space of real pth power integrable functions on [0,1], and Δ;, asusual, be the class of kth monotone functions.展开更多
A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vert...A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vertex.This concept was introduced by Tutte as an extension of face colorings,and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow,known as the 5-Flow Conjecture.This conjecture is verified for some graph classes and remains unresolved as of today.In this paper,we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow,which improves several known results.展开更多
A proper conflict-free k-coloring of a graph is a proper k-coloring in which each nonisolated vertex has a color that appears ex-actly once in its open neighborhood.A graph is PCF k-colorable if it admits a proper con...A proper conflict-free k-coloring of a graph is a proper k-coloring in which each nonisolated vertex has a color that appears ex-actly once in its open neighborhood.A graph is PCF k-colorable if it admits a proper conflict-free k-coloring.The PCF chromatic number of a graph G,denoted by χ_(pcf)(G),is the minimum k such that G is PCF k-colorable.Caro et al conjectured that for a connected graph G with maximum degreeΔ≥3,χ_(pcf)(G)≤Δ+1.One case in this conjecture,a connected graph with maximum degree 3 is PCF 4-colorable,can be derived from the result of Liu and Yu.Jiménez et al stated that the upper bound of PCF chromatic number of a graph G is max{5,x(G)}without a proof.In this paper,we give new proofs of the two results above and derive that for a connected graph G with maximum degreeΔ≥3,its complete subdivision is PCF(Δ+1)-colorable.展开更多
使用反例压缩算法,从反例中剔除冗余信息,从而使反例易于理解,是目前的研究热点.然而,目前压缩率最高的BFL（brute force lifting）算法,其时间开销过大.为此,提出一种基于悖论分析和增量式SAT（boolean satisfiablilty problem）的快...使用反例压缩算法,从反例中剔除冗余信息,从而使反例易于理解,是目前的研究热点.然而,目前压缩率最高的BFL（brute force lifting）算法,其时间开销过大.为此,提出一种基于悖论分析和增量式SAT（boolean satisfiablilty problem）的快速反例压缩算法.首先,根据反证法和排中律原理,该算法对每一个自由变量v,构造一个SAT问题,以测试v是否能够避免反例.而后对其中不可满足的SAT问题,进行悖论分析,抽取出导致悖论的变量集合.所有不属于该集合的变量,均可作为无关变量直接剔除.同时,该算法使用增量式SAT求解方法,以避免反复搜索冗余状态空间.理论分析和实验结果表明,与BFL算法相比,该算法能够在不损失压缩率的前提下获得1～2个数量级的加速.展开更多
基金Supported in part by Zhejiang Provincial Natural Science Foundation of Chinaa Special Research Fund ot" State Council of Education of China
文摘We adopt the following symbols and notations. Let C;be the class of all real continuous functions in [0,1] which have N continuousderivatives, L;0,1];be the space of real pth power integrable functions on [0,1], and Δ;, asusual, be the class of kth monotone functions.
文摘A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vertex.This concept was introduced by Tutte as an extension of face colorings,and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow,known as the 5-Flow Conjecture.This conjecture is verified for some graph classes and remains unresolved as of today.In this paper,we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow,which improves several known results.
基金Supported by the Youth Fund of Lanzhou Jiaotong University(1200061328)。
文摘A proper conflict-free k-coloring of a graph is a proper k-coloring in which each nonisolated vertex has a color that appears ex-actly once in its open neighborhood.A graph is PCF k-colorable if it admits a proper conflict-free k-coloring.The PCF chromatic number of a graph G,denoted by χ_(pcf)(G),is the minimum k such that G is PCF k-colorable.Caro et al conjectured that for a connected graph G with maximum degreeΔ≥3,χ_(pcf)(G)≤Δ+1.One case in this conjecture,a connected graph with maximum degree 3 is PCF 4-colorable,can be derived from the result of Liu and Yu.Jiménez et al stated that the upper bound of PCF chromatic number of a graph G is max{5,x(G)}without a proof.In this paper,we give new proofs of the two results above and derive that for a connected graph G with maximum degreeΔ≥3,its complete subdivision is PCF(Δ+1)-colorable.
文摘使用反例压缩算法,从反例中剔除冗余信息,从而使反例易于理解,是目前的研究热点.然而,目前压缩率最高的BFL（brute force lifting）算法,其时间开销过大.为此,提出一种基于悖论分析和增量式SAT（boolean satisfiablilty problem）的快速反例压缩算法.首先,根据反证法和排中律原理,该算法对每一个自由变量v,构造一个SAT问题,以测试v是否能够避免反例.而后对其中不可满足的SAT问题,进行悖论分析,抽取出导致悖论的变量集合.所有不属于该集合的变量,均可作为无关变量直接剔除.同时,该算法使用增量式SAT求解方法,以避免反复搜索冗余状态空间.理论分析和实验结果表明,与BFL算法相比,该算法能够在不损失压缩率的前提下获得1～2个数量级的加速.
