38559771
Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem
LetD=(V, E) be a digraph with vertex setVof sizenand arc setE. Foru?V, letd(u) denote the degree ofu. AMeyniel set Mis a subset ofVsuch thatd(u)+d(v)?2n?1 for every pair of nonadjacent verticesuandvbelonging toM. In this paper we show that ifDis strongly connected, then every Meyniel setMlies in a (directed) cycle, generalizing Meyniel's theorem. Our proof yields anO(|M|n4) algorithm for finding such a cycle. As a corollary it follows that ifDis strongly connected, thenDcontains a cycle through all vertices of degree ?nwhich generalizes a result of Shi for undirected graphs.
23519212
Lower bounds of length of longest cycles in graphs involving neighborhood unions
Let G be a simple graph of order n. Let NC = min {|N(x)∪N(y)|: xy ∉ E(G)}. Denote by c(G), the circumference of G, the length of a longest cycle in G. In this paper we settle a conjecture of Faudree, Gould, Jacobson and Schelp [4], proving that (a) if G is 3-connected, then c(G) ⩾ min {n, 3(NC + 1)/2}; and (b) if G is 4-connected, then c(G) ⩾ min {n, 2NC}. Two examples are given to show that both bounds are sharp.
42264207
A decision tree solution considering the decision maker's attitude
We extend the expected monetary value (EMV) method of the decision tree to include the decision maker's preference information. Considering the decision maker's profit and risk attitude respectively, a decision tree method with ordered weighted average (OWA) aggregation operator is proposed. With given profit and risk optimistic level, the payoff values of the alternatives can be aggregated with geometric OWA operator and BADD (BAsic Defuzzification Distribution) neat OWA operator. Some properties of these two kinds of OWA operators are analyzed. And the process of the approach is shown by an illustrative example.
16757439
Odd Hole Recognition in Graphs of Bounded Clique Size
In a graph $G$, an odd hole is an induced odd cycle of length at least 5. A clique of $G$ is a set of pairwise adjacent vertices. In this paper we consider the class ${\cal C}_k$ of graphs whose cliques have a size bounded by a constant $k$. Given a graph $G$ in ${\cal C}_k$, we show how to recognize in polynomial time whether $G$ contains an odd hole.
2229369
Recognizing Berge Graphs
A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(|V (G)|9). This is independent of the recent proof of the strong perfect graph conjecture.
32095656
Analyzing Outliers Cautiously
Outliers are difficult to handle because some of them can be measurement errors, while others may represent phenomena of interest, something "significant" from the viewpoint of the application domain. Statistical and computational methods have been proposed to detect outliers, but further analysis of outliers requires much relevant domain knowledge. In our previous work (1994), we suggested a knowledge-based method for distinguishing between the measurement errors and phenomena of interest by modeling "real measurements" - how measurements should be distributed in an application domain. In this paper, we make this distinction by modeling measurement errors instead. This is a cautious approach to outlier analysis, which has been successfully applied to a medical problem and may find interesting applications in other domains such as science, engineering, finance, and economics.
14452513
Spatial Operators for Evolving Dynamic Bayesian Networks from Spatio-temporal Data
Learning Bayesian networks from data has been studied extensively in the evolutionary algorithm communities [Larranaga96, Wong99]. We have previously explored extending some of these search methods to temporal Bayesian networks [Tucker01]. A characteristic of many datasets from medical to geographical data is the spatial arrangement of variables. In this paper we investigate a set of operators that have been designed to exploit the spatial nature of such data in order to learn dynamic Bayesian networks more efficiently. We test these operators on synthetic data generated from a Gaussian network where the architecture is based upon a Cartesian coordinate system, and real-world medical data taken from visual field tests of patients suffering from ocular hypertension.