24315827
On neighborhood condition for graphs to have [a, b]-factors
Let G be a graph of order n, and let a and b be integers such that 1 ≤ a > b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G) ≥ (k - 1) a, n ≥ (a + b)(k(a + b) - 2)/b, and |NG(x1) ∪ NG(x2) ∪..∪ NG(xk)| ≥ an/(a + b) for any independent subset {x1,x2 ..... xk} of V(G), where k ≥ 2, then G has an [a,b]-factor. This result is best possible in some sense.
27000668
On (g, f, n)-Critical Graphs
27085181
A new degree condition for graphs to have [a, b]-factor
Abstract Let t ( ⩾ 3 ) , a and b be integers with 0 ⩽ a b . A graph is called K 1 , t -free if it contains no K 1 , t as an induced subgraph. We prove that every K 1 , t -free G has an [ a , b ] -factor if its minimum degree is at least ( t - 1 ) ( a + 1 ) + b b b + a ( t - 1 ) 2 ( t - 1 ) - t - 1 b b + a ( t - 1 ) 2 ( t - 1 ) 2 - 1 . This degree condition is sharp.
11813663
Complete-factors and (g, f)-factors
A factor F of a graph is called a complete-factor if each component of F is complete. Let G be a graph, F be a complete-factor of G with @w(F)>=2 and f,g be two integer-valued functions defined on V(G) with f(x)>=g(x) for all [email protected]?V(G). It is proved that if @w(F)=0(mod2), or f(V(G)) even and f(x)=g(x)(mod2) for all [email protected]?V(G), and if G-V(C) has a (g,f)-factor for each component C of F, then G has a (g,f)-factor. We show that the results in this paper are best possible.
36793490
Code-coverage guided prioritized test generation
Most automatic test generation research focuses on generation of test data from pre-selected program paths or input domains or program specifications. This paper presents a methodology for a full solution to code-coverage-based test case generation, which includes code coverage-based path selection, test data generation and actual test case representation in program's original languages. We implemented this method in an automatic testing framework, eXVantage. Experimental results and industrial trials show that the framework is able to generate tests to achieve program line coverage from 20% to 98% with reduced overall testing effort. Our major contributions include an innovative coverage-based program prioritization algorithm, a novel path selection algorithm that takes into consideration program priority and functional calling relationship, and a constraint solver for test data generation that derives constraints from bytecode and solves complex constraints involving strings and dynamic objects.
925345
Attribute-Based Access Control with Hidden Policies and Hidden Credentials
In an open environment such as the Internet, the decision to collaborate with a stranger (e.g., by granting access to a resource) is often based on the characteristics (rather than the identity) of the requester, via digital credentials: access is granted if Alice's credentials satisfy Bob's access policy. The literature contains many scenarios in which it is desirable to carry out such trust negotiations in a privacy-preserving manner, i.e., so as minimize the disclosure of credentials and/or of access policies. Elegant solutions were proposed for achieving various degrees of privacy-preservation through minimal disclosure. In this paper, we present protocols that protect both sensitive credentials and sensitive policies. That is, Alice gets the resource only if she satisfies the policy, Bob does not learn anything about Alice's credentials (not even whether Alice got access), and Alice learns neither Bob's policy structure nor which credentials caused her to gain access. Our protocols are efficient in terms of communication and in rounds of interaction
36212113
Independent triangles covering given vertices of a graph
Let G be a simple graph of order n, k a positive integer with n≥3k and X a set of any k vertices of G. We show that if the minimum degree G)≥(n + k)=2, then G contains k independent triangles covering all vertices of X ; and if the minimum degree (G)≥(n+2k)=2, then G contains k independent triangles such that each triangle contains exactly one vertex of X . The bounds on the minimum degree of G in above results are sharp. Some conjectures about independent triangles covering some given vertices are proposed.
5901027
Cycles Containing Many Vertices of Subsets in 1-Tough Graphs with Large Degree Sums
2012673
Mining the smallest association rule set for predictions
Mining transaction databases for association rules usually generates a large number of rules, most of which are unnecessary when used for subsequent prediction. In this paper we define a rule set for a given transaction database that is much smaller than the association rule set but makes the same predictions as the association rule set by the confidence priority. We call this subset the informative rule set. The informative rule set is not constrained to particular target items; and it is smaller than the non-redundant association rule set. We present an algorithm to directly generate the informative rule set, i.e., without generating all frequent itemsets first, and that accesses the database less often than other unconstrained direct methods. We show experimentally that the informative rule set is much smaller than both the association rule set and the non-redundant association rule set, and that it can be generated more efficiently.