32007375
Interpolation theorems for graphs, hypergraphs and matroids
Abstract Let P and Q be, respectively, hereditary and cohereditary properties defined on the subsets of a finite set S . We first prove that several functions related to P and Q interpolate over some families of subsets of S . By using this we then derive a number of interpolation results for graphs, hypergraphs and matroids.
14780024
Fuzzy causal networks: general model, inference, and convergence
In this paper, we first propose a general framework for fuzzy causal networks (FCNs). Then, we study the dynamics and convergence of such general FCNs. We prove that any general FCN with constant weight matrix converges to a limit cycle or a static state, or the trajectory of the FCN is not repetitive. We also prove that under certain conditions a discrete state general FCN converges to its limit cycle or static state in O(n) steps, where n is the number of vertices of the FCN. This is in striking contrast with the exponential running time 2/sup n/, which is accepted widely for classic FCNs.
25346055
Almost Covers Of 2-Arc Transitive Graphs
Let Γ be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition ℬ with block size v. Let Γℬ be the quotient graph of Γ relative to ℬ and Γ[B,C] the bipartite subgraph of Γ induced by adjacent blocks B,C of ℬ. In this paper we study such graphs for which Γℬ is connected, (G, 2)-arc transitive and is almost covered by Γ in the sense that Γ[B,C] is a matching of v-1 ≥ 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case Γℬ ≅Kv+1 is covered by results of Gardiner and Praeger. We consider here the general case where Γℬ ≇Kv+1, and prove that, for some even integer n ≥ 4, Γℬ is a near n-gonal graph with respect to a certain G-orbit on n-cycles of Γℬ. Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient Γℬ of a graph with these properties. (A near n-gonal graph is a connected graph Σ of girth at least 4 together with a set ℰ of n-cycles of Σ such that each 2-arc of Σ is contained in a unique member of ℰ.)
35890566
On Isomorphisms of Minimal Cayley Graphs and Digraphs
Abstract. A Cayley graph or digraph Cay(G,S) is called a CI-graph of G if, for any T⊂G, Cay(G,S)≅Cay(G,T) if and only if Sσ=T for some σ∈Aut(G). The aim of this paper is to characterize finite abelian groups for which all minimal Cayley graphs and digraphs are CI-graphs.
5800162
A sequential coloring algorithm for finite sets
Abstract Let X be a finite set and P a hereditary property associated with the subsets of X . A partition of X into n subsets each with property P is said to be a P-n -coloring of X . The minimum n such that a P-n -coloring of X exists is defined to be the P -chromatic number of X . In this paper we give a sequential coloring algorithm for P -coloring X . From the algorithm we then get a few upper bounds for the P -chromatic number. In particular, we generalize the Welsh-Powell upper bound for ordinary chromatic number to the case of P -chromatic number of any finite set X .
18154847
Dynamic domination in fuzzy causal networks
This paper presents a dynamic domination theory for fuzzy causal networks (FCN). There are three major contributions. First, we propose a new inference procedure based on dominating sets. Second, we introduce the concepts of dynamic and minimal dynamic dominating sets (DDS and MDDS) in an FCN. To reflect changes of dominance with time, we also introduce the concept of a dynamic dominating process (DDP) that has significant implications in many real-world problems. We pay a special attention to the minimal dynamic dominating process (MDDP) and develop rules for generating DDP and MDDP. Third, we investigate dynamic dominating sets with extended feedback, which we call effective dynamic dominating sets (EDDS), and related effective dynamic dominating process (EDDP). This study unveils a very important phenomenon in FCN: At any time t, either an EDDS exists or there is a dramatic change of the states of vertices. In the latter case we also identify the special structure of the sub-FCN induced by active vertices.
1466117
Redundancy and Robustness of the AS-level Internet topology and its models
A comparison between the topological properties of the measured Internet topology, at the autonomous system level (AS graph), and the equivalent graphs generated by two different power law topology generators are presented. Only one of the synthetic generators reproduces the tier connectivity of the AS graph.
13962685
Intra-personal kernel space for face recognition
Intra-personal space modeling proposed by Moghaddam et al. has been successfully applied in face recognition. In their work the regular principal subspaces are derived from the intra-personal spacce using a principal componen analysis and embedded in a probabilistic formulation. In this paper, we derive the principal subspace from the intro-personal kernel space by developing a probabilistic analysis for kernel principal components for face recognition. We test this algorithm on a subset of the FERET database with illumination and facial expression variations. The recognition performance demonstrates its advantage over other traditional subspace approaches.
9649594
Probabilistic Human Recognition from Video
This paper presents a method for incorporating temporal information in a video sequence for the task of human recognition. A time series state space model, parameterized by a tracking state vector and a recognizing identity variable, is proposed to simultaneously characterize the kinematics and identity. Two sequential importance sampling (SIS) methods, a brute-force version and an efficient version, are developed to provide numerical solutions to the model. The joint distribution of both state vector and identity variable is estimated at each time instant and then propagated to the next time instant. Marginalization over the state vector yields a robust estimate of the posterior distribution of the identity variable. Due to the propagation of identity and kinematics, a degeneracy in posterior probability of the identity variable is achieved to give improved recognition. This evolving behavior is characterized using changes in entropy. The effectiveness of this approach is illustrated using experimental results on low resolution face data and upper body data.
10785532
Probabilistic recognition of human faces from video
Most present face recognition approaches recognize faces based on still images. We present a novel approach to recognize faces in video. In that scenario, the face gallery may consist of still images or may be derived from a videos. For evidence integration we use classical Bayesian propagation over time and compute the posterior distribution using sequential importance sampling. The probabilistic approach allows us to handle uncertainties in a systematic manner. Experimental results using videos collected by NIST/USF and CMU illustrate the effectiveness of this approach in both still-to-video and video-to-video scenarios with appropriate model choices.
11542871
Illuminating light field: image-based face recognition across illuminations and poses
We present an image-based method for face recognition across different illuminations and different poses, where the term 'image-based' means that only 2D images are used and no explicit 3D models are needed. As face recognition across illuminations and poses involves three factors, namely identity, illumination, and pose, generalizations from known identities to novel identities, from known illuminations to novel illuminations, and from known poses to unknown poses are desired. Our approach, called the illuminating light field, derives an identity signature that is invariant to illuminations and poses, where a subspace encoding is assumed for the identity, a Lambertain reflectance model for the illumination, and a light field model for the poses. Experimental results using the PIE database demonstrate the effectiveness of the proposed approach.