To see the other types of publications on this topic, follow the link: Complete Call Graph.
Journal articles on the topic 'Complete Call Graph'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Complete Call Graph.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Kaliraj, K., V. Kowsalya, and Vernold Vivin. "On star coloring of Mycielskians." Indonesian Journal of Combinatorics 2, no. 2 (December 21, 2018): 82. http://dx.doi.org/10.19184/ijc.2018.2.2.3.
Full textAbstract:
<p>In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph <span class="math"><em>G</em></span> into a new graph <span class="math"><em>μ</em>(<em>G</em>)</span>, we now call the Mycielskian of <span class="math"><em>G</em></span>, which has the same clique number as <span class="math"><em>G</em></span> and whose chromatic number equals <span class="math"><em>χ</em>(<em>G</em>) + 1</span>. In this paper, we find the star chromatic number for the Mycielskian graph of complete graphs, paths, cycles and complete bipartite graphs.</p>
2
Badawi, Ayman, and Roswitha Rissner. "Ramsey numbers of partial order graphs (comparability graphs) and implications in ring theory." Open Mathematics 18, no. 1 (December 31, 2020): 1645–57. http://dx.doi.org/10.1515/math-2020-0085.
Full textAbstract:
Abstract For a partially ordered set (A,\le ) , let {G}_{A} be the simple, undirected graph with vertex set A such that two vertices a\ne b\in A are adjacent if either a\le b or b\le a . We call {G}_{A} the partial order graph or comparability graph of A. Furthermore, we say that a graph G is a partial order graph if there exists a partially ordered set A such that G={G}_{A} . For a class {\mathcal{C}} of simple, undirected graphs and n, m\ge 1 , we define the Ramsey number { {\mathcal R} }_{{\mathcal{C}}}(n,m) with respect to {\mathcal{C}} to be the minimal number of vertices r such that every induced subgraph of an arbitrary graph in {\mathcal{C}} consisting of r vertices contains either a complete n-clique {K}_{n} or an independent set consisting of m vertices. In this paper, we determine the Ramsey number with respect to some classes of partial order graphs. Furthermore, some implications of Ramsey numbers in ring theory are discussed.
3
Voorhees, Burton, and Bergerud Ryder. "Simple graph models of information spread in finite populations." Royal Society Open Science 2, no. 5 (May 2015): 150028. http://dx.doi.org/10.1098/rsos.150028.
Full textAbstract:
We consider several classes of simple graphs as potential models for information diffusion in a structured population. These include biases cycles, dual circular flows, partial bipartite graphs and what we call ‘single-link’ graphs. In addition to fixation probabilities, we study structure parameters for these graphs, including eigenvalues of the Laplacian, conductances, communicability and expected hitting times. In several cases, values of these parameters are related, most strongly so for partial bipartite graphs. A measure of directional bias in cycles and circular flows arises from the non-zero eigenvalues of the antisymmetric part of the Laplacian and another measure is found for cycles as the value of the transition probability for which hitting times going in either direction of the cycle are equal. A generalization of circular flow graphs is used to illustrate the possibility of tuning edge weights to match pre-specified values for graph parameters; in particular, we show that generalizations of circular flows can be tuned to have fixation probabilities equal to the Moran probability for a complete graph by tuning vertex temperature profiles. Finally, single-link graphs are introduced as an example of a graph involving a bottleneck in the connection between two components and these are compared to the partial bipartite graphs.
4
Corò, Federico, Gianlorenzo D'Angelo, and Cristina M. Pinotti. "Adding Edges for Maximizing Weighted Reachability." Algorithms 13, no. 3 (March 18, 2020): 68. http://dx.doi.org/10.3390/a13030068.
Full textAbstract:
In this paper, we consider the problem of improving the reachability of a graph. We approach the problem from a graph augmentation perspective, in which a limited set size of edges is added to the graph to increase the overall number of reachable nodes. We call this new problem the Maximum Connectivity Improvement (MCI) problem. We first show that, for the purpose of solve solving MCI, we can focus on Directed Acyclic Graphs (DAG) only. We show that approximating the MCI problem on DAG to within any constant factor greater than 1 − 1 / e is NP -hard even if we restrict to graphs with a single source or a single sink, and the problem remains NP -complete if we further restrict to unitary weights. Finally, this paper presents a dynamic programming algorithm for the MCI problem on trees with a single source that produces optimal solutions in polynomial time. Then, we propose two polynomial-time greedy algorithms that guarantee ( 1 − 1 / e ) -approximation ratio on DAGs with a single source, a single sink or two sources.
5
ORENSHTEIN, TAL, and IGOR SHINKAR. "Greedy Random Walk." Combinatorics, Probability and Computing 23, no. 2 (November 20, 2013): 269–89. http://dx.doi.org/10.1017/s0963548313000552.
Full textAbstract:
We study a discrete time self-interacting random process on graphs, which we call greedy random walk. The walker is located initially at some vertex. As time evolves, each vertex maintains the set of adjacent edges touching it that have not yet been crossed by the walker. At each step, the walker, being at some vertex, picks an adjacent edge among the edges that have not traversed thus far according to some (deterministic or randomized) rule. If all the adjacent edges have already been traversed, then an adjacent edge is chosen uniformly at random. After picking an edge the walker jumps along it to the neighbouring vertex. We show that the expected edge cover time of the greedy random walk is linear in the number of edges for certain natural families of graphs. Examples of such graphs include the complete graph, even degree expanders of logarithmic girth, and the hypercube graph. We also show that GRW is transient in$\mathbb{Z}^d$for alld≥ 3.
6
Simonyi, Gábor. "On Colorful Edge Triples in Edge-Colored Complete Graphs." Graphs and Combinatorics 36, no. 6 (September 9, 2020): 1623–37. http://dx.doi.org/10.1007/s00373-020-02214-4.
Full textAbstract:
Abstract An edge-coloring of the complete graph $$K_n$$ K n we call F-caring if it leaves no F-subgraph of $$K_n$$ K n monochromatic and at the same time every subset of |V(F)| vertices contains in it at least one completely multicolored version of F. For the first two meaningful cases, when $$F=K_{1,3}$$ F = K 1 , 3 and $$F=P_4$$ F = P 4 we determine for infinitely many n the minimum number of colors needed for an F-caring edge-coloring of $$K_n$$ K n . An explicit family of $$2\lceil \log _2 n\rceil $$ 2 ⌈ log 2 n ⌉ 3-edge-colorings of $$K_n$$ K n so that every quadruple of its vertices contains a totally multicolored $$P_4$$ P 4 in at least one of them is also presented. Investigating related Ramsey-type problems we also show that the Shannon (OR-)capacity of the Grötzsch graph is strictly larger than that of the cycle of length 5.
7
Górska, Joanna, and Zdzisław Skupień. "A partial refining of the Erdős-Kelly regulation." Opuscula Mathematica 39, no. 3 (2019): 355–60. http://dx.doi.org/10.7494/opmath.2019.39.3.355.
Full textAbstract:
The aim of this note is to advance the refining of the Erdős-Kelly result on graphical inducing regularization. The operation of inducing regulation (on graphs or multigraphs) with prescribed maximum vertex degree is originated by D. König in 1916. As is shown by Chartrand and Lesniak in their textbook Graphs & Digraphs (1996), an iterated construction for graphs can result in a regularization with many new vertices. Erdős and Kelly have presented (1963, 1967) a simple and elegant numerical method of determining for any simple \(n\)-vertex graph \(G\) with maximum vertex degree \(\Delta\), the exact minimum number, say \(\theta =\theta(G)\), of new vertices in a \(\Delta\)-regular graph \(H\) which includes \(G\) as an induced subgraph. The number \(\theta(G)\), which we call the cost of regulation of \(G\), has been upper-bounded by the order of \(G\), the bound being attained for each \(n\ge4\), e.g. then the edge-deleted complete graph \(K_n-e\) has \(\theta=n\). For \(n\ge 4\), we present all factors of \(K_n\) with \(\theta=n\) and next \(\theta=n-1\). Therein in case \(\theta=n-1\) and \(n\) odd only, we show that a specific extra structure, non-matching, is required.
8
Garamvölgyi, Dániel, and Tibor Jordán. "Graph Reconstruction from Unlabeled Edge Lengths." Discrete & Computational Geometry 66, no. 1 (February 26, 2021): 344–85. http://dx.doi.org/10.1007/s00454-021-00275-7.
Full textAbstract:
AbstractA d-dimensional framework is a pair (G, p), where $$G=(V,E)$$ G = ( V , E ) is a graph and p is a map from V to $$\mathbb {R}^d$$ R d . The length of an edge $$uv\in E$$ u v ∈ E in (G, p) is the distance between p(u) and p(v). The framework is said to be globally rigid in $$\mathbb {R}^d$$ R d if every other d-dimensional framework (G, q), in which the corresponding edge lengths are the same, is congruent to (G, p). In a recent paper Gortler, Theran, and Thurston proved that if every generic framework (G, p) in $$\mathbb {R}^d$$ R d is globally rigid for some graph G on $$n\ge d+2$$ n ≥ d + 2 vertices (where $$d\ge 2$$ d ≥ 2 ), then already the set of (unlabeled) edge lengths of a generic framework (G, p), together with n, determine the framework up to congruence. In this paper we investigate the corresponding unlabeled reconstruction problem in the case when the above generic global rigidity property does not hold for the graph. We provide families of graphs G for which the set of (unlabeled) edge lengths of any generic framework (G, p) in d-space, along with the number of vertices, uniquely determine the graph, up to isomorphism. We call these graphs weakly reconstructible. We also introduce the concept of strong reconstructibility; in this case the labeling of the edges is also determined by the set of edge lengths of any generic framework. For $$d=1,2$$ d = 1 , 2 we give a partial characterization of weak reconstructibility as well as a complete characterization of strong reconstructibility of graphs. In particular, in the low-dimensional cases we describe the family of weakly reconstructible graphs that are rigid but not redundantly rigid.
9
Manuel, Paul, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj, and Elizabeth Thomas. "Strong edge geodetic problem in networks." Open Mathematics 15, no. 1 (October 3, 2017): 1225–35. http://dx.doi.org/10.1515/math-2017-0101.
Full textAbstract:
Abstract Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. [Math. Comput. Modelling, 1993, 17, 89-95]. Here we introduce a variation of the geodetic problem and call it strong edge geodetic problem. We illustrate how this problem is evolved from social transport networks. It is shown that the strong edge geodetic problem is NP-complete. We derive lower and upper bounds for the strong edge geodetic number and demonstrate that these bounds are sharp. We produce exact solutions for trees, block graphs, silicate networks and glued binary trees without randomization.
10
Zou, Deqing, Yueming Wu, Siru Yang, Anki Chauhan, Wei Yang, Jiangying Zhong, Shihan Dou, and Hai Jin. "IntDroid." ACM Transactions on Software Engineering and Methodology 30, no. 3 (May 2021): 1–32. http://dx.doi.org/10.1145/3442588.
Full textAbstract:
Android, the most popular mobile operating system, has attracted millions of users around the world. Meanwhile, the number of new Android malware instances has grown exponentially in recent years. On the one hand, existing Android malware detection systems have shown that distilling the program semantics into a graph representation and detecting malicious programs by conducting graph matching are able to achieve high accuracy on detecting Android malware. However, these traditional graph-based approaches always perform expensive program analysis and suffer from low scalability on malware detection. On the other hand, because of the high scalability of social network analysis, it has been applied to complete large-scale malware detection. However, the social-network-analysis-based method only considers simple semantic information (i.e., centrality) for achieving market-wide mobile malware scanning, which may limit the detection effectiveness when benign apps show some similar behaviors as malware. In this article, we aim to combine the high accuracy of traditional graph-based method with the high scalability of social-network-analysis--based method for Android malware detection. Instead of using traditional heavyweight static analysis, we treat function call graphs of apps as complex social networks and apply social-network--based centrality analysis to unearth the central nodes within call graphs. After obtaining the central nodes, the average intimacies between sensitive API calls and central nodes are computed to represent the semantic features of the graphs. We implement our approach in a tool called IntDroid and evaluate it on a dataset of 3,988 benign samples and 4,265 malicious samples. Experimental results show that IntDroid is capable of detecting Android malware with an F-measure of 97.1% while maintaining a True-positive Rate of 99.1%. Although the scalability is not as fast as a social-network-analysis--based method (i.e., MalScan ), compared to a traditional graph-based method, IntDroid is more than six times faster than MaMaDroid . Moreover, in a corpus of apps collected from GooglePlay market, IntDroid is able to identify 28 zero-day malware that can evade detection of existing tools, one of which has been downloaded and installed by more than ten million users. This app has also been flagged as malware by six anti-virus scanners in VirusTotal, one of which is Symantec Mobile Insight .
11
Li, Yan, Tingjian Ge, and Cindy Chen. "Data stream event prediction based on timing knowledge and state transitions." Proceedings of the VLDB Endowment 13, no. 10 (June 2020): 1779–92. http://dx.doi.org/10.14778/3401960.3401973.
Full textAbstract:
We study a practical problem of predicting the upcoming events in data streams using a novel approach. Treating event time orders as relationship types between event entities, we build a dynamic knowledge graph and use it to predict future event timing. A unique aspect of this knowledge graph embedding approach for prediction is that we enhance conventional knowledge graphs with the notion of "states"---in what we call the ephemeral state nodes---to characterize the state of a data stream over time. We devise a complete set of methods for learning relevant events, for building the event-order graph stream from the original data stream, for embedding and prediction, and for theoretically bounding the complexity. We evaluate our approach with four real world stream datasets and find that our method results in high precision and recall values for event timing prediction, ranging between 0.7 and nearly 1, significantly outperforming baseline approaches. Moreover, due to our choice of efficient translation-based embedding, the overall throughput that the stream system can handle, including continuous graph building, training, and event predictions, is over one thousand to sixty thousand tuples per second even on a personal computer---which is especially important in resource constrained environments, including edge computing.
12
Angelini, Patrizio, Peter Eades, Seok-Hee Hong, Karsten Klein, Stephen Kobourov, Giuseppe Liotta, Alfredo Navarra, and Alessandra Tappini. "Graph Planarity by Replacing Cliques with Paths." Algorithms 13, no. 8 (August 13, 2020): 194. http://dx.doi.org/10.3390/a13080194.
Full textAbstract:
This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, we prove that h-Clique2Path Planarity is NP-complete even when h=4 and G is a simple 3-plane graph, while it can be solved in linear time when G is a simple 1-plane graph, for any value of h. Our results contribute to the growing fields of hybrid planarity and of graph drawing beyond planarity.
13
LARROSA, JAVIER, and GABRIEL VALIENTE. "Constraint satisfaction algorithms for graph pattern matching." Mathematical Structures in Computer Science 12, no. 4 (August 2002): 403–22. http://dx.doi.org/10.1017/s0960129501003577.
Full textAbstract:
Graph pattern matching is a central problem in many application fields. Since it is NP-complete, we cannot expect to find algorithms with a good worst-case performance. However, there is still room for general procedures with a good average performance. In this paper we explore four different solving approaches within the constraint satisfaction framework, and introduce a new algorithm, which we call nRF+. The algorithm is a refinement of really full look ahead that takes advantage of the problem structure in order to enhance the look ahead procedure. We give a formal proof that nRF+ is superior to the other approaches in terms of number of visited nodes. An additional contribution of this paper is the introduction of a new benchmark for testing algorithms in this domain. It is formed by a large set of well-defined graphs of very diverse nature. In this benchmark, we show that nRF+ can efficiently solve a broad range of problems, while still leaving many problem instances unsolved. The use of this challenging benchmark is encouraged for future algorithms evaluation.
14
Cheng, Binlin, Jinjun Liu, Jiejie Chen, Shudong Shi, Xufu Peng, Xingwen Zhang, and Haiqing Hai. "MoG: Behavior-Obfuscation Resistance Malware Detection." Computer Journal 62, no. 12 (June 4, 2019): 1734–47. http://dx.doi.org/10.1093/comjnl/bxz033.
Full textAbstract:
Abstract Malware brings a big security threat on the Internet today. With the great increasing malware attacks. Behavior-based detection approaches are one of the major method to detect zero-day malware. Such approaches often use API calls to represent the behavior of malware. Unfortunately, behavior-based approaches suffer from behavior obfuscation attacks. In this paper, we propose a novel malware detection approach that is both effective and efficient. First, we abstract the API call to object operation. And then we generate the object operation dependency graph based on these object operations. Finally, we construct the family dependency graph for a malware family. Our approach use family dependency graph to represent the behavior of malware family. The evaluation results show that our approach can provide a complete resistance to all types of behavior obfuscation attacks, and outperforms existing behavior-based approaches in terms of better effectiveness and efficiency.
15
TOWBER, JACOB. "DIRECTED GRAPHS AND KRONECKER INVARIANTS OF PAIRS OF MATRICES." Journal of Knot Theory and Its Ramifications 17, no. 01 (January 2008): 75–132. http://dx.doi.org/10.1142/s0218216508005926.
Full textAbstract:
Call two pairs (M,N) and (M′,N′) of m × n matrices over a field K, simultaneously K-equivalent if there exist square invertible matrices S,T over K, with M′ = SMT and N′ = SNT. Kronecker [2] has given a complete set of invariants for simultaneous equivalence of pairs of matrices. Associate in the natural way to a finite directed graph Γ, with v vertices and e edges, an ordered pair (M,N) of e × v matrices of zeros and ones. It is natural to try to compute the Kronecker invariants of such a pair (M,N), particularly since they clearly furnish isomorphism-invariants of Γ. Let us call two graphs "linearly equivalent" when their two corresponding pairs are simultaneously equivalent. There have existed, since 1890, highly effective algorithms for computing the Kronecker invariants of pairs of matrices of the same size over a given field [1,2,5,6] and in particular for those arising in the manner just described from finite directed graphs. The purpose of the present paper, is to compute directly these Kronecker invariants of finite directed graphs, from elementary combinatorial properties of the graphs. A pleasant surprise is that these new invariants are purely rational — indeed, integral, in the sense that the computation needed to decide if two directed graphs are linearly equivalent only involves counting vertices in various finite graphs constructed from each of the given graphs — and does not involve finding the irreducible factorization of a polynomial over K (in apparent contrast both to the familiar invariant-computations of graphs furnished by the eigenvalues of the connection matrix, and to the isomorphism problem for general pairs of matrices).
16
FELDHEIM, OHAD N. "Monotonicity of Avoidance Coupling on KN." Combinatorics, Probability and Computing 26, no. 1 (June 3, 2016): 16–23. http://dx.doi.org/10.1017/s0963548316000195.
Full textAbstract:
Answering a question by Angel, Holroyd, Martin, Wilson and Winkler [1], we show that the maximal number of non-colliding coupled simple random walks on the complete graph KN, which take turns, moving one at a time, is monotone in N. We use this fact to couple [N/4] such walks on KN, improving the previous Ω(N/log N) lower bound of Angel et al. We also introduce a new generalization of simple avoidance coupling which we call partially ordered simple avoidance coupling, and provide a monotonicity result for this extension as well.
17
Farshi, Mehdi, Bijan Davvaz, and Saeed Mirvakili. "Degree hypergroupoids associated with hypergraphs." Filomat 28, no. 1 (2014): 119–29. http://dx.doi.org/10.2298/fil1401119f.
Full textAbstract:
In this paper, we present some connections between graph theory and hyperstructure theory. In this regard, we construct a hypergroupoid by defining a hyperoperation on the set of degrees of vertices of a hypergraph and we call it a degree hypergroupoid. We will see that the constructed hypergroupoid is always anHv-group. We will investigate some conditions on a degree hypergroupoid to have a hypergroup. Further, we study the degree hypergroupoid associated with Cartesian product of hypergraphs. Finally, the fundamental relation and complete parts of a degree hypergroupoid are studied.
18
WILDS, ROY, and LEON GLASS. "AN ATLAS OF ROBUST, STABLE, HIGH-DIMENSIONAL LIMIT CYCLES." International Journal of Bifurcation and Chaos 19, no. 12 (December 2009): 4055–96. http://dx.doi.org/10.1142/s0218127409025225.
Full textAbstract:
We present a method for constructing dynamical systems with robust, stable limit cycles in arbitrary dimensions. Our approach is based on a correspondence between dynamics in a class of differential equations and directed graphs on the n-dimensional hypercube (n-cube). When the directed graph contains a certain type of cycle, called a cyclic attractor, then a stable limit cycle solution of the differential equations exists. A novel method for constructing regulatory systems that we call minimal regulatory networks from directed graphs facilitates investigation of limit cycles in arbitrarily high dimensions. We identify two families of cyclic attractors that are present for all dimensions n ≥ 3: cyclic negative feedback and sequential disinhibition. For each, we obtain explicit representations for the differential equations in arbitrary dimension. We also provide a complete listing of minimal regulatory networks, a representative differential equation, and a bifurcation analysis for each cyclic attractor in dimensions 3–5. This work joins discrete concepts of symmetry and classification with analysis of differential equations useful for understanding dynamics in complex biological control networks.
19
Ferreira, Rodrigo S., Emilio Vital Brazil, Reinaldo Silva, and Renato Cerqueira. "Seismic graph analysis to aid seismic interpretation." Interpretation 7, no. 3 (August 1, 2019): SE81—SE92. http://dx.doi.org/10.1190/int-2018-0185.1.
Full textAbstract:
During the seismic interpretation process, geoscientists rely on their experience and visual analysis to assess the similarity between seismic sections. However, evaluating all of the seismic sections in a 3D survey can be a time-consuming task. When interpreters are working on a data set, a common procedure is to divide the cube in increasingly finer grids until they are satisfied with the result of the interpretation. We have developed a method based on graph theory and image texture in which we represent a seismic data set as a complete weighted undirected graph — which we call a seismic graph. The vertices of this graph represent the seismic sections, and the weight of the edges represents the distance between the texture feature vectors of the vertices they connect, allowing for a powerful yet concise representation of potentially large data sets. We have investigated the potential of graph analysis to build an adaptive grid that is more likely to capture the underlying structures present in a survey, providing a tool for a faster and more precise interpretation. The main idea is that such a grid would be finer in regions with more geologic variations and coarser otherwise. To demonstrate the capabilities of our technique, we apply it on a public data set called Netherlands F3. Using our method, we suggest which seismic sections — key sections — should be considered in the interpretation process. The results of our experiments indicate that our methodology has great potential to aid the seismic interpretation process.
20
Whitfield, Carl A., Peter Latimer, Alex Horsley, Jim M. Wild, Guilhem J. Collier, and Oliver E. Jensen. "Spectral graph theory efficiently characterizes ventilation heterogeneity in lung airway networks." Journal of The Royal Society Interface 17, no. 168 (July 2020): 20200253. http://dx.doi.org/10.1098/rsif.2020.0253.
Full textAbstract:
This paper introduces a linear operator for the purposes of quantifying the spectral properties of transport within resistive trees, such as airflow in lung airway networks. The operator, which we call the Maury matrix, acts only on the terminal nodes of the tree and is equivalent to the adjacency matrix of a complete graph summarizing the relationships between all pairs of terminal nodes. We show that the eigenmodes of the Maury operator have a direct physical interpretation as the relaxation, or resistive, modes of the network. We apply these findings to both idealized and image-based models of ventilation in lung airway trees and show that the spectral properties of the Maury matrix characterize the flow asymmetry in these networks more concisely than the Laplacian modes, and that eigenvector centrality in the Maury spectrum is closely related to the phenomenon of ventilation heterogeneity caused by airway narrowing or obstruction. This method has applications in dimensionality reduction in simulations of lung mechanics, as well as for characterization of models of the airway tree derived from medical images.
21
Lee, Sanghack, Juan D. Correa, and Elias Bareinboim. "Identifiability from a Combination of Observations and Experiments." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 09 (April 3, 2020): 13677–80. http://dx.doi.org/10.1609/aaai.v34i09.7119.
Full textAbstract:
We study the problem of causal identification from an arbitrary collection of observational and experimental distributions, and substantive knowledge about the phenomenon under investigation, which usually comes in the form of a causal graph. We call this problem g-identifiability, or gID for short. In this paper, we introduce a general strategy to prove non-gID based on thickets and hedgelets, which leads to a necessary and sufficient graphical condition for the corresponding decision problem. We further develop a procedure for systematically computing the target effect, and prove that it is sound and complete for gID instances. In other words, the failure of the algorithm in returning an expression implies that the target effect is not computable from the available distributions. Finally, as a corollary of these results, we show that do-calculus is complete for the task of g-identifiability.
22
Yang, Zhao Hong, Qing Xiao, Yun Zhan Gong, Da Hai Jin, and Ya Wen Wang. "The Research of an Abstract Semantic Framework for Defect Detecting." Advanced Materials Research 186 (January 2011): 536–40. http://dx.doi.org/10.4028/www.scientific.net/amr.186.536.
Full textAbstract:
This paper proposes a non-relational abstract semantic framework. It uses interval set to represent the value of numerical variables and complete lattice to represent Boolean variables and reference variables. It presents the abstract computation method of basic expressions and the nodes of control flow graph. It uses function summaries to represent the context information of function call needed by defects detecting. Based on the results of abstract computation, it uses extended state machine to define defect patterns and proposes a path-sensitive method based on dataflow analysis to detect defects. It avoids the combination explosion of full path analysis by merging the conditions of identical property state at join points in the CFG. Practical test results show that the proposed methods have features of high efficiency, low false positive and low false negative.
23
Merly, E. Ebin Raja, and J. Suthiesh Goldy. "Even Star Decomposition of Complete Bipartite Graphs." Journal of Mathematics Research 8, no. 5 (September 27, 2016): 101. http://dx.doi.org/10.5539/jmr.v8n5p101.
Full textAbstract:
<p><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;">A decomposition (</span><span><span style="font-family: 宋体; font-size: medium;">G</span></span><sub><span style="font-family: 宋体; font-size: small;">1</span></sub><span style="font-family: 宋体; font-size: medium;">, </span><span><span style="font-family: 宋体; font-size: medium;">G</span></span><sub><span style="font-family: 宋体; font-size: small;">2</span></sub><span style="font-family: 宋体; font-size: medium;">, </span><span><span style="font-family: 宋体; font-size: medium;">G</span></span><sub><span style="font-family: 宋体; font-size: small;">3</span></sub><span style="font-family: 宋体; font-size: medium;">,</span></span><span><span style="font-size: medium;">… </span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;">, </span><span><span style="font-family: 宋体; font-size: medium;">G</span></span><sub><span style="font-family: 宋体; font-size: small;">n</span></sub><span style="font-family: 宋体; font-size: medium;">) of a graph G is an Arithmetic Decomposition(AD) if |</span><span><span style="font-family: 宋体; font-size: medium;">E</span></span><span style="font-family: 宋体; font-size: medium;">(</span><span><span style="font-family: 宋体; font-size: medium;">G</span></span><sub><span style="font-family: 宋体; font-size: small;">i</span></sub><span style="font-family: 宋体; font-size: medium;">)| = a + (i – 1)d for all i = </span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;">1, 2,</span></span><span><span style="font-size: medium;">… </span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;">, n and a, d</span></span><span><span style="font-size: medium;">∈</span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;">Z</span><sup><span style="font-family: 宋体; font-size: small;">+</span></sup><span style="font-family: 宋体; font-size: medium;">. Clearly q = </span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;">n/2</span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;"> [2a + (n – 1)d]. The AD is a CMD if a = 1 and d = 1. In this paper we introduced the new concept Even Decomposition of graphs. If a = 2 and d = 2 in AD, then q = n(n + 1). That is, the number of edges of G </span><span><span style="font-family: 宋体; font-size: medium;">is the sum of first n even numbers 2, 4, 6,</span></span></span><span><span style="font-size: medium;">… </span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;">, 2n. Thus we call the AD with a =</span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;"> 2 and</span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;"> d = 2 as Even Decomposition. Since the number of edges of each subgraph of G is even, we denote the Even Decomposition as (</span><span><span style="font-family: 宋体; font-size: medium;">G</span><sub><span style="font-family: 宋体; font-size: small;">2</span></sub></span><span style="font-family: 宋体; font-size: medium;">, </span><span><span style="font-family: 宋体; font-size: medium;">G</span><sub><span style="font-family: 宋体; font-size: small;">4</span></sub></span><span style="font-family: 宋体; font-size: medium;">,</span></span><span><span style="font-size: medium;">… </span></span><span lang="EN-US"><span style="font-family: 宋体; font-size: medium;">, </span><span><span style="font-family: 宋体; font-size: medium;">G</span></span><sub><span style="font-family: 宋体; font-size: small;">2n</span></sub><span style="font-family: 宋体; font-size: medium;">). </span></span></p><p><span lang="EN-US"><span style="font-family: Calibri; font-size: medium;"> </span></span></p>
24
Hoffmann, J. "Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+." Journal of Artificial Intelligence Research 41 (June 2, 2011): 155–229. http://dx.doi.org/10.1613/jair.3276.
Full textAbstract:
The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work, it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results -- the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains -- we herein answer this question in the affirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish ``easy'' domains from ``hard'' ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.
25
Lanchier, N., and N. Taylor. "Galam's bottom-up hierarchical system and public debate model revisited." Advances in Applied Probability 47, no. 03 (September 2015): 668–92. http://dx.doi.org/10.1017/s0001867800048783.
Full textAbstract:
This paper is concerned with the bottom-up hierarchical system and public debate model proposed by Galam (2008), as well as a spatial version of the public debate model. In all three models, there is a population of individuals who are characterized by one of two competing opinions, say opinion −1 and opinion +1. This population is further divided into groups of common size s. In the bottom-up hierarchical system, each group elects a representative candidate, whereas in the other two models, all the members of each group discuss at random times until they reach a consensus. At each election/discussion, the winning opinion is chosen according to Galam's majority rule: the opinion with the majority of representatives wins when there is a strict majority, while one opinion, say opinion −1, is chosen by default in the case of a tie. For the public debate models we also consider the following natural updating rule that we call proportional rule: the winning opinion is chosen at random with a probability equal to the fraction of its supporters in the group. The three models differ in term of their population structure: in the bottom-up hierarchical system, individuals are located on a finite regular tree, in the nonspatial public debate model, they are located on a complete graph, and in the spatial public debate model, they are located on the d-dimensional regular lattice. For the bottom-up hierarchical system and nonspatial public debate model, Galam studied the probability that a given opinion wins under the majority rule and, assuming that individuals' opinions are initially independent, making the initial number of supporters of a given opinion a binomial random variable. The first objective of this paper is to revisit Galam's result, assuming that the initial number of individuals in favor of a given opinion is a fixed deterministic number. Our analysis reveals phase transitions that are sharper under our assumption than under Galam's assumption, particularly with small population size. The second objective is to determine whether both opinions can coexist at equilibrium for the spatial public debate model under the proportional rule, which depends on the spatial dimension.
26
Lanchier, N., and N. Taylor. "Galam's bottom-up hierarchical system and public debate model revisited." Advances in Applied Probability 47, no. 3 (September 2015): 668–92. http://dx.doi.org/10.1239/aap/1444308877.
Full textAbstract:
This paper is concerned with the bottom-up hierarchical system and public debate model proposed by Galam (2008), as well as a spatial version of the public debate model. In all three models, there is a population of individuals who are characterized by one of two competing opinions, say opinion −1 and opinion +1. This population is further divided into groups of common size s. In the bottom-up hierarchical system, each group elects a representative candidate, whereas in the other two models, all the members of each group discuss at random times until they reach a consensus. At each election/discussion, the winning opinion is chosen according to Galam's majority rule: the opinion with the majority of representatives wins when there is a strict majority, while one opinion, say opinion −1, is chosen by default in the case of a tie. For the public debate models we also consider the following natural updating rule that we call proportional rule: the winning opinion is chosen at random with a probability equal to the fraction of its supporters in the group. The three models differ in term of their population structure: in the bottom-up hierarchical system, individuals are located on a finite regular tree, in the nonspatial public debate model, they are located on a complete graph, and in the spatial public debate model, they are located on the d-dimensional regular lattice. For the bottom-up hierarchical system and nonspatial public debate model, Galam studied the probability that a given opinion wins under the majority rule and, assuming that individuals' opinions are initially independent, making the initial number of supporters of a given opinion a binomial random variable. The first objective of this paper is to revisit Galam's result, assuming that the initial number of individuals in favor of a given opinion is a fixed deterministic number. Our analysis reveals phase transitions that are sharper under our assumption than under Galam's assumption, particularly with small population size. The second objective is to determine whether both opinions can coexist at equilibrium for the spatial public debate model under the proportional rule, which depends on the spatial dimension.
27
Comte, Céline, and Jan-Pieter Dorsman. "Pass-and-swap queues." Queueing Systems 98, no. 3-4 (April 12, 2021): 275–331. http://dx.doi.org/10.1007/s11134-021-09700-3.
Full textAbstract:
AbstractOrder-independent (OI) queues, introduced by Berezner et al. (Queueing Syst 19(4):345–359, 1995), expanded the family of multi-class queues that are known to have a product-form stationary distribution by allowing for intricate class-dependent service rates. This paper further broadens this family by introducing pass-and-swap (P&S) queues, an extension of OI queues where, upon a service completion, the customer that completes service is not necessarily the one that leaves the system. More precisely, we supplement the OI queue model with an undirected graph on the customer classes, which we call a swapping graph, such that there is an edge between two classes if customers of these classes can be swapped with one another. When a customer completes service, it passes over customers in the remainder of the queue until it finds a customer it can swap positions with, that is, a customer whose class is a neighbor in the graph. In its turn, the customer that is ejected from its position takes the position of the next customer it can be swapped with, and so on. This is repeated until a customer can no longer find another customer to be swapped with; this customer is the one that leaves the queue. After proving that P&S queues have a product-form stationary distribution, we derive a necessary and sufficient stability condition for (open networks of) P&S queues that also applies to OI queues. We then study irreducibility properties of closed networks of P&S queues and derive the corresponding product-form stationary distribution. Lastly, we demonstrate that closed networks of P&S queues can be applied to describe the dynamics of new and existing load-distribution and scheduling protocols in clusters of machines in which jobs have assignment constraints.
28
Scuderi, Richard A., David B. Ebenstein, Ying-Wai Lam, Jana Kraft, and Sabrina L. Greenwood. "Inclusion of grape marc in dairy cattle rations alters the bovine milk proteome." Journal of Dairy Research 86, no. 2 (May 2019): 154–61. http://dx.doi.org/10.1017/s0022029919000372.
Full textAbstract:
AbstractGrape marc (GPM) is a viticulture by-product that is rich in secondary compounds, including condensed tannins (CT), and is used as a supplement in livestock feeding practices. The aim of this study was to determine whether feeding GPM to lactating dairy cows would alter the milk proteome through changes in nitrogen (N) partitioning. Ten lactating Holstein cows were fed a total mixed ration (TMR) top-dressed with either 1.5 kg dry matter (DM)/cow/day GPM (GPM group; n = 5) or 2.0 kg DM/cow/day of a 50:50 beet pulp: soy hulls mix (control group; n = 5). Characterization of N partitioning and calculation of N partitioning was completed through analysis of plasma urea-N, urine, feces, and milk urea-N. Milk samples were collected for general composition analysis, HPLC quantification of the high abundance milk proteins (including casein isoforms, α-lactalbumin, and β-lactoglobulin) and liquid chromatography tandem mass spectrometry (LC-MS/MS) analysis of the low abundance protein enriched milk fraction. No differences in DMI, N parameters, or calculated N partitioning were observed across treatments. Dietary treatment did not affect milk yield, milk protein or fat content or yield, or the concentrations of high abundance milk proteins quantified by HPLC analysis. Of the 127 milk proteins that were identified by LC-MS/MS analysis, 16 were affected by treatment, including plasma proteins and proteins associated with the blood-milk barrier, suggesting changes in mammary passage. Immunomodulatory proteins, including butyrophilin subfamily 1 member 1A and serum amyloid A protein, were higher in milk from GPM-fed cows. Heightened abundance of bioactive proteins in milk caused by dietary-induced shifts in mammary passage could be a feasible method to enhance the healthfulness of milk for both the milk-fed calf and human consumer. Additionally, the proteome shifts observed in this trial could provide a starting point for the identification of biomarkers suitable for use as indicators of mammary function.
29
Emmenegger, J. F., D. Chable, H. A. Nour Eldin, and H. Knolle. "Sraffa and Leontief Revisited: Mathematical Methods and Models of a Circular Economy." Cybernetics and Computer Technologies, no. 2 (July 24, 2020): 86–99. http://dx.doi.org/10.34229/2707-451x.20.2.9.
Full textAbstract:
Introduction. Sometimes new results in one scientific field can help to study quite other branches. In the new book we observe application of various mathematical methods to study circular economics. The purpose of the paper is to give information about the new book “SRAFFA AND LEONTIEF REVISITED: Mathematical methods and models of a circular economy”. The academic editor Walter de Gruyter-Oldenbourg has published this monography in January 2020 in English language. Results. This book contributes to the increasing call for a comprehensive perception of economic production processes. The book is dedicated to Wassily Leontief’s concept of Input-Output Analysis and to Piero Sraffa's seminal book “Production of Commodities by Means of Commodities”. Single product and joint production industries of a circular economy are described, consequently using matrix algebra. The central role of the Perron-Frobenius Theorem for non-negative matrices, specially Perron-Frobenius eigenvalues and eigenvectors is revealed as a common basis of Sraffa’s and Leontief’s approaches and applied to clarify the basic economic assumptions which are inherent to economic production processes. Conclusions. The book addresses young researchers wishing to explore the foundations of circular economy, practitioners wishing to examine the potential of Sraffa’s price models in connection to Leontief’s Input-Output analysis. Advanced undergraduate, graduate, PhD students and their instructors in economics, political science or applied mathematics, who seek to understand Sraffa and the recent developments of the circular economy of inter industrial and national economy will find numerous examples with complete solutions, presented by a rich, formal, mathematical methodology, revealing the economic content of the results. Detailed examples and visualizing graphs are presented for applications of various mathematical methods. Keywords: Input-Output analysis, circular economy, Perron-Frobenius Theorem, non-negative matrix.
30
Landon, Emily, Gretchen Pacholek, Demetria Runjo, Sylvia Garcia-Houchins, Jessica P. Ridgway, Stephen G. Weber, Vera Chu, Rachel Marrs, and Allison H. Bartlett. "Sustained Improvement in Hand Hygiene Compliance Using a Decentralized, Technology-Based Approach." Open Forum Infectious Diseases 4, suppl_1 (2017): S408. http://dx.doi.org/10.1093/ofid/ofx163.1020.
Full textAbstract:
Abstract Background We aimed to use weekly PI calls in conjunction with 24/7 hand hygiene monitoring technology (HHMT) to engage front-line Intensive Care Unit (ICUs) clinicians in improving Hand Hygiene (HH) compliance Methods HHMT is used to monitor aggregate, unit-based HH compliance in real time and displayed on monitors at the nursing stations at our academic medical center. After installation and validation were completed, unit-based teams of nursing and physician leadership joined weekly 15-minute HH PI calls to discuss their previous week’s compliance rate, next steps in their own PI plan, and share successes and failures. Calls were suspended for 6 months and restarted in early 2017. Results Graph representation of weekly HH compliance rates for the ICUs are shown in figure 1. Units AandB underwent physical moves during the break, Unit C had no change, and Unit D moved and consolidated with other ICUs constituting a major change in personnel and patient population. Each ICU participated in 84 calls and recorded approx. 50,000–100,000 HH opportunities during each month resulting in over 8 million opportunities for HH compliance recorded during the call-in periods. Unit A had an average compliance of 39% for the first 4 weeks of calls and 64% during the same 4 week period one year later (P < 0.0001). After 6 months without the calls, HH compliance was 48% (P < 0.0001 compared with baseline compliance) and unit A implemented 20 separate PI interventions over the course of the calls. Compliance was also significantly improved (P < 0.0001 for all comparison to baseline) for units B, C, and D (Unit B: 42% baseline, 71% at 1 year, 67% after the break, 23 interventions; Unit C: 54% baseline, 58% at 1 year, 59% after the break, 19 interventions; Unit D: 41% at baseline, 56% after 1 year, 49% after the break, 19 interventions). Attendance was >90% for nursing leadership and <25% for physician leadership. Conclusion Weekly 15-minute calls were successful in engaging local nursing leadership to undertake performance improvement interventions and significantly improved HH compliance that was sustained over 18 months of calls and did not drop back to baseline even after a 6 month break. Disclosures E. Landon, GOJO: Speaker, travel expenses for speaking; 
 J. P. Ridgway, Gilead FOCUS: Grant Investigator, Grant recipient; A. H. Bartlett, CVS Caremark: Consultant, Consulting fee
31
Singh, Prachi, Amanda Lucas, and Monica Nayakwadi Singer. "1153. UV-C Technology Is an Effective Adjunct to Terminal Cleaning in Environmental Pathogen Reduction in a Tertiary Pediatric Hospital." Open Forum Infectious Diseases 5, suppl_1 (November 2018): S346—S347. http://dx.doi.org/10.1093/ofid/ofy210.986.
Full textAbstract:
Abstract Background Effective environmental surface cleaning plays a vital role in reducing transmission of hospital-acquired infections. There remains a paucity of data in the pediatric literature regarding environmental pathogen reduction utilizing UV-C light. The objective of this study was to evaluate the reduction of environmental pathogens using UV-C light (Clorox Optimum-UV) as an adjunct to terminal cleaning in a free-standing tertiary pediatric hospital. Methods Upon patient discharge, a subset of patient rooms were tested for pathogens. Surface swabs were collected from high touch surfaces (call button, telemetry monitor, door handle, flush handle of toilet, faucet, bed rail, phone, keyboard pad, mouse, side table, dresser, and light switch). After terminal cleaning of the room, per hospital protocol the Clorox Optimum-UV completed one or two cycles of 5 minutes each depending on the dimensions of the room. Post-UV-C surface swabs were obtained from the same high touch areas in the room. Total colony count was reported from each of the surfaces swabbed. Swabs were streaked onto non-selective agar and incubated at 30-35oC for 72–96 hours. Mean plate colony count was determined manually and reported as CFU/swab. Data analysis was performed in Minitab 18.1. Fisher least significant difference (LSD) test was used to describe the difference between total bacterial counts at each time point (Pre-clean: dirty room, Post-clean: pre-UV-C/post-terminal clean, Post-UV: post UV-C light cycle). Results Mean total colony counts prior to cleaning the room was 92.3 CFU (33 surfaces), Pre-UV-C light 45.6 CFU and post-UV-C light 5.8 CFU (64 surfaces). Total bacterial counts are represented in Graphs 1 and 2. Upon multivariate analysis, the time the sample was taken (preclean, postclean, or post-UV) was the single explanatory variable for the differences seen in the means of total bacterial counts (P = 0). Conclusion Our study demonstrates that UV-C disinfection is a highly effective adjunctive cleaning method with standard terminal cleaning to reduce bacterial burden from environmental surfaces. Disclosures A. Lucas, Clorox: Research Contractor, Grant recipient. M. Nayakwadi Singer, Clorox: Grant Investigator, Grant recipient.
32
Michels, Alison, Laura L. Swystun, Silvia Albánez, Jeffrey Mewburn, Kate Sponagle, and David Lillicrap. "Histones Induce Endothelial Von Willebrand Factor Release and Subsequent Platelet Capture in In Vitro and In Vivo Models." Blood 124, no. 21 (December 6, 2014): 2768. http://dx.doi.org/10.1182/blood.v124.21.2768.2768.
Full textAbstract:
Abstract Thrombosis is the leading cause of mortality worldwide and can result from uncontrolled immune activation in inflammatory conditions. Von Willebrand factor (VWF) is an acute phase glycoprotein that mediates primary hemostasis by binding to platelets. It is stored in platelets and in Weibel-Palade bodies (WPB) in endothelial cells. Cell-free DNA (CF-DNA) and histones are released during cell damage and have been shown to stimulate innate immune and pro-thrombotic responses including, in the case of histones, thrombocytopenia in mice and VWF release due to platelet activation/aggregation. We recently demonstrated the correlation between VWF and CF-DNA plasma levels in human and mouse models of chronic inflammation associated with aging. In these studies we investigate the influence of CF-DNA and histones on VWF release and platelet-binding in murine and endothelial cell models. C57BL6 mice received a retro-orbital injection of unfractionated (UFH), lysine-rich (H1) or arginine-rich (H3/H4) calf thymus histone (20 mg/kg), calf thymus DNA (4 mg/kg) or saline and blood was collected 1 hr post-injection from the inferior vena cava into buffered citrate. Platelet count was quantified from whole blood via a complete blood count. Blood-outgrowth endothelial cells (BOEC) from normal individuals were stimulated with UFH, H1, H3/H4, DNA and DNA/histone combinations (25 µg/mL) for 75 min. VWF and ANG-2 (stored exclusively in WPB) was quantified from plasma and BOEC media by ELISA and results expressed as fold-change ± SD. To visualize the influence of histone on platelet binding to BOEC surface associated VWF, BOEC were seeded onto collagen coated flow chamber slides. BOEC were stimulated for 20 min. with UFH (50 µg/mL) or histamine (25µM). Washed platelets were labelled with DiOC6 and flowed at a shear rate of 500s-1 over BOEC for 10 min. VWF-platelet strings (≥ 3 consecutive platelets) were quantified from still images obtained post-flow. In C57BL6 mice, VWF:Ag levels were significantly increased by UFH infusion (1.31±0.17, p=0.0015, n=8) but not DNA (1.09±0.19, p=0.20, n=10) relative to saline controls (1.00±0.16, n=14). H1 (1.64±0.20, n=5) mediated a greater VWF release than H3/H4 (1.21±0.20, p=0.01, n=6) and UFH (p=0.006). As previously described, we observed that UFH (0.74±0.08, p=0.0005), H1 (0.73±0.09, p=0.0011) and H3/H4 (0.87±0.14, p=0.08) induced thrombocytopenia in normal mice. ANG-2 levels were also significantly higher in H3/H4 (1.38±0.20, p=0.004) than saline (1.00±0.20) treated mice. Mice receiving UFH (1.25±0.31, p=0.13) and H1 (1.36±0.33, p=0.07) also had elevated ANG-2 levels although not statistically significant. Taken together this data suggests that both platelet and endothelial cells may contribute to VWF release upon histone-treatment. In vitro treatment of BOEC with H1 induced greater VWF (2.13±0.61, p=0.004) and ANG-2 (2.66±0.60, p=0.004) release as compared to the unstimulated condition (1.00±0.36). Interestingly, when BOEC were stimulated with UFH and DNA together we observed an increase in ANG-2 release (1.39±0.23, n=4, p=0.02) compared to unstimulated BOEC, but not in VWF:Ag when the cells were treated with each stimulus alone. As histones have been shown to bind to VWF, we hypothesize that these results could be explained by an impaired detection of VWF that is partially mitigated by the addition of DNA to the system. Using the in vitro flow chamber model, we observed significantly more VWF-platelet strings formed when cells were pre-incubated with UFH (5.51±0.97 strings, p=0.002) than when not stimulated (0.72±0.77 strings) (Figure 1). The ability of histones to activate platelets may also contribute to VWF-platelet string formation. Histones, but not DNA, stimulate the release of VWF from endothelial cells and platelets and facilitate platelet capture by endothelial VWF in a flow chamber model. As CF-DNA may serve as a surrogate marker for plasma histone levels, the correlation between CF-DNA and VWF:Ag we have previously observed in chronic inflammatory conditions, may be related in part to histone-induced VWF release from platelet and endothelial cell stores. These experiments demonstrate that histones induce VWF release in vivo and suggest a novel connection between the innate immune and hemostatic systems. Figure 1 Representative images taken after flow experiment. Arrows indicate VWF-platelet strings. Graph is expressed in mean ± SD (**p=0.0025). Figure 1. Representative images taken after flow experiment. Arrows indicate VWF-platelet strings. Graph is expressed in mean ± SD (**p=0.0025). Disclosures No relevant conflicts of interest to declare.
33
Nauman, Syed Khalid, and Basmah H. Shafee. "A class of zero divisor rings in which every graph is precisely the union of a complete graph and a complete bipartite graph." Open Mathematics 13, no. 1 (January 25, 2015). http://dx.doi.org/10.1515/math-2015-0050.
Full textAbstract:
AbstractRecently, an interest is developed in estimating genus of the zero-divisor graph of a ring. In this note we investigate genera of graphs of a class of zero-divisor rings (a ring in which every element is a zero divisor). We call a ring R to be right absorbing if for a; b in R, ab is not 0, then ab D a. We first show that right absorbing rings are generalized right Klein 4-rings of characteristic two and that these are non-commutative zero-divisor local rings. The zero-divisor graph of such a ring is proved to be precisely the union of a complete graph and a complete bipartite graph. Finally, we have estimated lower and upper bounds of the genus of such a ring.
34
Cori, Robert, and Yvan Le Borgne. "On the ranks of configurations on the complete graph." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AS,..., Proceedings (January 1, 2013). http://dx.doi.org/10.46298/dmtcs.2332.
Full textAbstract:
International audience We consider the parameter rank introduced for graph configurations by M. Baker and S. Norine. We focus on complete graphs and obtain an efficient algorithm to determine the rank for these graphs. The analysis of this algorithm leads to the definition of a parameter on Dyck words, which we call prerank. We prove that the distribution of area and prerank on Dyck words of given length $2n$ leads to a polynomial with variables $q,t$ which is symmetric in these variables. This polynomial is different from the $q,t-$Catalan polynomial studied by A. Garsia, J. Haglund and M. Haiman.
35
Okamoto, Yoshio, Yota Otachi, and Ryuhei Uehara. "On bipartite powers of bigraphs." Discrete Mathematics & Theoretical Computer Science Vol. 14 no. 2, Graph Theory (August 5, 2012). http://dx.doi.org/10.46298/dmtcs.576.
Full textAbstract:
Graph Theory International audience The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general.
36
Chiaselotti, G., T. Gentile, and F. G. Infusino. "Some classifications of graphs with respect to a set adjacency relation." Discrete Mathematics, Algorithms and Applications, September 21, 2020, 2050089. http://dx.doi.org/10.1142/s1793830920500895.
Full textAbstract:
For any finite simple undirected graph [Formula: see text], we consider the binary relation [Formula: see text] on the powerset [Formula: see text] of its vertex set given by [Formula: see text] if [Formula: see text], where [Formula: see text] denotes the neighborhood of a vertex [Formula: see text]. We call the above relation set adiacence dependency (sa)-dependency of [Formula: see text]. With the relation [Formula: see text] we associate an intersection-closed family [Formula: see text] of vertex subsets and the corresponding induced lattice [Formula: see text], which we call sa-lattice of [Formula: see text]. Through the equality of sa-lattices, we introduce an equivalence relation [Formula: see text] between graphs and propose three different classifications of graphs based on such a relation. Furthermore, we determine the sa-lattice for various graph families, such as complete graphs, complete bipartite graphs, cycles and paths and, next, we study such a lattice in relation to the Cartesian and the tensor product of graphs, verifying that in most cases it is a graded lattice. Finally, we provide two algorithms, namely, the T-DI ALGORITHM and the O-F ALGORITHM, in order to provide two different computational ways to construct the sa-lattice of a graph. For the O-F ALGORITHM we also determine its computational complexity.
37
Alizadeh, Hadi, and Didem Gözüpek. "Almost well-dominated bipartite graphs with minimum degree at least two." RAIRO - Operations Research, April 27, 2020. http://dx.doi.org/10.1051/ro/2020042.
Full textAbstract:
A dominating set in a graph $G=(V,E)$ is a set $S$ such that every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$. While the minimum cardinality of a dominating set in $G$ is called the domination number of $G$ denoted by $\gamma(G)$, the maximum cardinality of a minimal dominating set in $G$ is called the upper domination number of $G$ denoted by $\Gamma(G)$. We call the difference between these two parameters the \textit{domination gap} of $G$ and denote it by $\mu_d(G) = \Gamma(G) - \gamma(G)$. While a graph $G$ with $\mu_d(G)=0$ is said to be a \textit{well-dominated} graph, we call a graph $G$ with $\mu_d(G)=1$ an \textit{almost well-dominated} graph. In this work, we first establish an upper bound for the cardinality of bipartite graphs with $\mu_d(G)=k$, where $k\geq1$, and minimum degree at least two. We then provide a complete structural characterization of almost well-dominated bipartite graphs with minimum degree at least two. While the results by Finbow et al.~\cite{domination} imply that a 4-cycle is the only well-dominated bipartite graph with minimum degree at least two, we prove in this paper that there exist precisely 31 almost well-dominated bipartite graphs with minimum degree at least two.
38
Bérczi, Kristóf, Attila Bernáth, and Máté Vizer. "A Note on $\mathtt{V}$-free 2-matchings." Electronic Journal of Combinatorics 23, no. 4 (November 25, 2016). http://dx.doi.org/10.37236/5258.
Full textAbstract:
Motivated by a conjecture of Liang, we introduce a restricted path packing problem in bipartite graphs that we call a $\mathtt{V}$-free $2$-matching. We verify the conjecture through a weakening of the hypergraph matching problem. We close the paper by showing that it is NP-complete to decide whether one of the color classes of a bipartite graph can be covered by a $\mathtt{V}$-free $2$-matching.
39
Chen, Xuegang, and Jing Huang. "Uniquely monopolar-partitionable block graphs." Discrete Mathematics & Theoretical Computer Science Vol. 16 no. 2, PRIMA 2013 (May 6, 2014). http://dx.doi.org/10.46298/dmtcs.2073.
Full textAbstract:
Special issue PRIMA 2013 International audience As a common generalization of bipartite and split graphs, monopolar graphs are defined in terms of the existence of certain vertex partitions. It has been shown that to determine whether a graph has such a partition is NP-complete for general graphs and polynomial for several classes of graphs. In this paper, we investigate graphs that admit a unique such partition and call them uniquely monopolar-partitionable graphs. By employing a tree trimming technique, we obtain a characterization of uniquely monopolar-partitionable block graphs. Our characterization implies a polynomial time algorithm for recognizing them.
40
Shetty, Jyoti, and G. Sudhakara. "Binomial incidence matrix of a semigraph." Discrete Mathematics, Algorithms and Applications, October 20, 2020, 2150017. http://dx.doi.org/10.1142/s1793830921500178.
Full textAbstract:
A semigraph, defined as a generalization of graph by Sampathkumar, allows an edge to have more than two vertices. The idea of multiple vertices on edges gives rise to multiplicity in every concept in the theory of graphs when generalized to semigraphs. In this paper, we define a representing matrix of a semigraph [Formula: see text] and call it binomial incidence matrix of the semigraph [Formula: see text]. This matrix, which becomes the well-known incidence matrix when the semigraph is a graph, represents the semigraph uniquely, up to isomorphism. We characterize this matrix and derive some results on the rank of the matrix. We also show that a matrix derived from the binomial incidence matrix satisfies a result in graph theory which relates incidence matrix of a graph and adjacency matrix of its line graph. We extend the concept of “twin vertices” in the theory of graphs to semigraph theory, and characterize them. Finally, we derive a systematic approach to show that the binomial incidence matrix of any semigraph on [Formula: see text] vertices can be obtained from the incidence matrix of the complete graph [Formula: see text].
41
"Double Arithmetic Odd Decomposition [DAOD] of Some Complete 4-Partite Graphs." International Journal of Innovative Technology and Exploring Engineering 9, no. 2 (December 10, 2019): 3902–7. http://dx.doi.org/10.35940/ijitee.b7814.129219.
Full textAbstract:
Let G be a finite, connected, undirected graph without loops or multiple edges. If G1 , G2 , . . . ,Gn are connected edge – disjoint subgraphs of G with E(G) = E(G1 ) E(G2 ) . . . E(Gn), then { G1 , G2 , . . . , Gn} is said to be a decomposition of G. The concept of Arithmetic Odd Decomposition [AOD] was introduced by E. Ebin Raja Merly and N. Gnanadhas . A decomposition {G1 , G2 , . . . , Gn } G is said to be Arithmetic Decomposition if each Gi is connected and | E(Gi )| = a+ (i – 1) d , for 1 i n and a, d ℤ . When a =1 and d = 2, we call the Arithmetic Decomposition as Arithmetic Odd Decomposition . A decomposition { G1 , G3 , . . . , G2n-1} of G is said to be AOD if | E (Gi ) | = i , i = 1, 3, . . . , 2n-1. In this paper, we introduce a new concept called Double Arithmetic Odd Decomposition [DAOD]. A graph G is said to have Double Arithmetic Odd Decomposition [DAOD] if G can be decomposed into 2k subgraphs { 2G1 , 2G3 , . . . , 2G2k-1 } such that each Gi is connected and | E (Gi ) | = i , i = 1, 3, . . . , 2k-1. Also we investigate DAOD of some complete 4-partite graphs such as K2,2,2,m , K2,4,4,m and K1 ,2,4,m .
42
Cori, Robert, and Yvan Le Borgne. "On Computation of Baker and Norine’s Rank on Complete Graphs." Electronic Journal of Combinatorics 23, no. 1 (February 19, 2016). http://dx.doi.org/10.37236/4350.
Full textAbstract:
The paper by M. Baker and S. Norine in 2007 introduced a new parameter on configurations of graphs and gave a new result in the theory of graphs which has an algebraic geometry flavor. This result was called Riemann-Roch formula for graphs since it defines a combinatorial version of divisors and their ranks in terms of configurations on graphs. The so called chip firing game on graphs and the sandpile model in physics play a central role in this theory. In this paper we present an algorithm for the determination of the rank of configurations for the complete graph $K_n$. This algorithm has linear arithmetic complexity. The analysis of number of iterations in a less optimized version of this algorithm leads to an apparently new parameter which we call the prerank. This parameter and the parameter dinv provide an alternative description to some well known $q,t$-Catalan numbers. Restricted to a natural subset of configurations, the two natural statistics degree and rank lead to a distribution which is described by a generating function which, up to a change of variables and a rescaling, is a symmetric fraction involving two copies of Carlitz $q$-analogue of the Catalan numbers. In annex, we give an alternative presentation of the theorem of Baker and Norine in purely combinatorial terms.
43
Konvalinka, Matjaž, and Igor Pak. "Cayley and Tutte polytopes." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AR,..., Proceedings (January 1, 2012). http://dx.doi.org/10.46298/dmtcs.3055.
Full textAbstract:
International audience Cayley polytopes were defined recently as convex hulls of Cayley compositions introduced by Cayley in 1857. In this paper we resolve Braun's conjecture, which expresses the volume of Cayley polytopes in terms of the number of connected graphs. We extend this result to a two-variable deformations, which we call Tutte polytopes. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph. Our approach is based on an explicit triangulation of the Cayley and Tutte polytope. We prove that simplices in the triangulations correspond to labeled trees and forests. The heart of the proof is a direct bijection based on the neighbors-first search graph traversal algorithm. Les polytopes de Cayley ont été définis récemment comme des ensembles convexes de compositions de Cayley introduits par Cayley en 1857. Dans ce papier, nous résolvons la conjecture de Braun. Cette dernière exprime le volume du polytopes de Cayley en termes du nombre de graphes connexes. Nous étendons ce résultat à des déformations de polytopes de Cayley à deux variables, à savoir les polytopes de Tutte. Le volume de ces derniers est donnè par une évaluation du polynôme de Tutte du graphe complet. Notre approche est basée sur une triangulation explicite des polytopes de Cayley et Tutte. Nous démontrons que les simplexes de ces triangulations correspondent à des arbres marqués. La pierre angulaire de notre démonstration est une bijection directe basées sur l'algorithme de la recherche du premier voisin sur le graphe.
44
Hajiabolhassan, Hossein, and Farokhlagha Moazami. "Secure frameproof codes through biclique covers." Discrete Mathematics & Theoretical Computer Science Vol. 14 no. 2, Graph Theory (December 4, 2012). http://dx.doi.org/10.46298/dmtcs.585.
Full textAbstract:
Graph Theory International audience For a binary code Γ of length v, a v-word w produces by a set of codewords {w1,...,wr}⊆Γ if for all i=1,...,v, we have wi∈{w1i,...,wri} . We call a code r-secure frameproof of size t if |Γ|=t and for any v-word that is produced by two sets C1 and C2 of size at most r then the intersection of these sets is nonempty. A d-biclique cover of size v of a graph G is a collection of v-complete bipartite subgraphs of G such that each edge of G belongs to at least d of these complete bipartite subgraphs. In this paper, we show that for t≥2r, an r-secure frameproof code of size t and length v exists if and only if there exists a 1-biclique cover of size v for the Kneser graph KG(t,r) whose vertices are all r-subsets of a t-element set and two r-subsets are adjacent if their intersection is empty. Then we investigate some connection between the minimum size of d-biclique covers of Kneser graphs and cover-free families, where an (r,w;d) cover-free family is a family of subsets of a finite set such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. Also, we present an upper bound for 1-biclique covering number of Kneser graphs.
45
Bowen, Matt, Ander Lamaison, and Alp Müyesser. "Finding Unavoidable Colorful Patterns in Multicolored Graphs." Electronic Journal of Combinatorics 27, no. 4 (October 2, 2020). http://dx.doi.org/10.37236/8184.
Full textAbstract:
We provide multicolored and infinite generalizations for a Ramsey-type problem raised by Bollobás, concerning colorings of $K_n$ where each color is well-represented. Let $\chi$ be a coloring of the edges of a complete graph on $n$ vertices into $r$ colors. We call $\chi$ $\varepsilon$-balanced if all color classes have $\varepsilon$ fraction of the edges. Fix some graph $H$, together with an $r$-coloring of its edges. Consider the smallest natural number $R_\varepsilon^r(H)$ such that for all $n\geq R_\varepsilon^r(H)$, all $\varepsilon$-balanced colorings $\chi$ of $K_n$ contain a subgraph isomorphic to $H$ in its coloring. Bollobás conjectured a simple characterization of $H$ for which $R_\varepsilon^2(H)$ is finite, which was later proved by Cutler and Montágh. Here, we obtain a characterization for arbitrary values of $r$, as well as asymptotically tight bounds. We also discuss generalizations to graphs defined on perfect Polish spaces, where the corresponding notion of balancedness is each color class being non-meagre.
46
Bensmail, Julien, Romaric Duvignau, and Sergey Kirgizov. "The complexity of deciding whether a graph admits an orientation with fixed weak diameter." Discrete Mathematics & Theoretical Computer Science Vol. 17 no. 3, Graph Theory (February 17, 2016). http://dx.doi.org/10.46298/dmtcs.2161.
Full textAbstract:
International audience An oriented graph $\overrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $\overrightarrow{G}$, there are directed paths joining $u$ and $v$ in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have length at most $k$, we call $\overrightarrow{G}$ $k$-weak (resp. $k$-strong). We consider several problems asking whether an undirected graph $G$ admits orientations satisfying some connectivity and distance properties. As a main result, we show that deciding whether $G$ admits a $k$-weak orientation is NP-complete for every $k \geq 2$. This notably implies the NP-completeness of several problems asking whether $G$ is an extremal graph (in terms of needed colours) for some vertex-colouring problems.
47
Serra, Thiago, Teng Huang, Arvind U. Raghunathan, and David Bergman. "Template-Based Minor Embedding for Adiabatic Quantum Optimization." INFORMS Journal on Computing, September 21, 2021. http://dx.doi.org/10.1287/ijoc.2021.1065.
Full textAbstract:
Quantum annealing (QA) can be used to quickly obtain near-optimal solutions for quadratic unconstrained binary optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms into the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum odd cycle transversals (OCTs). One of the formulations presented is exact and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller. Summary of Contribution: Our work combines classical and quantum computing for operations research by showing that integer linear programming can be successfully used as a preprocessing step for adiabatic quantum optimization. We use it to determine how a quadratic unconstrained binary optimization problem can be solved by a quantum annealer in which the qubits are coupled as in a Chimera graph, such as in the quantum annealers currently produced by D-Wave Systems. The paper also provides a timely introduction to adiabatic quantum computing and related work on minor embeddings.
48
"Malware Detection by Risky Zone “Signature” Extraction from API Calls String Transformation using (AOSSR) Technique." International Journal of Recent Technology and Engineering 8, no. 5 (January 30, 2020): 2865–75. http://dx.doi.org/10.35940/ijrte.e6260.018520.
Full textAbstract:
Low accuracy of malware detection exists in malware detectors that are based on various malware representation architectures due to several problems as in case of API call graph construction and matching algorithms, where a major issue of building a precise call graph from the information collected about malware samples, also graph matching algorithms are having NP-Complete Problems and slow because of their computational complexity [1], [2]. Moreover, increasing the malware detection accuracy based on API call graphs by enhancing the graph matching and construction algorithms, experiences more computational time taken for matching process and in construction process as there are many graphs created which makes it so difficult to fetch or identify the malware (Elhadi et al., 2013) [3]. It has been further argued by (Li et al., 2018) that in case of malevolent activities, it is comparatively intricate to find whether the software will fall under the spell of malicious occurrences or not, since the duty to determine whether the conduct of a program is malicious is quite complex [4]. This research proposes enhancement of API String-based representation technique through the implementation of a malware detection framework that adopts String-based representation of the malware signature which is a compact representation of the malware risky zone where only the set of API calls representing the actual malware behaviour is accounted in the String using Absolute Order Signature String Representation technique (AOSSR) to represent the malware Strings resulting in a better performance of malware detection accuracy. The Methodology this research work follows mainly composed of three phases. The first phase deals with the conversion of the known malware samples from text format to string format. The second phase addresses the extractaction of the risky zone of an input file which is the file that needs to be checked, by the help of the file signatures already been presented in the database. The third phase addresses how to match two strings efficiency. The Application of the research is very clear as last experiment conducted on 515 malware samples demonstrates that the proposed malware detection architecture has 98% accuracy and 0 false positive rates. Comparing three families, using Analysis of Variance (ANOVA) test it is proven there is no significant difference (p>0.05) in the detection rate of algorithm across the three families of malwares. The algorithms performance is consistent. The result also shows that the Receiver Operating Characteristics (ROC) curves display a better True Positives Rate (TPR) for the proposed architecture over the previous attempts, which reflect significant improvement of TPR.
49
Marciniszyn, Martin, Dieter Mitsche, and Miloš Stojaković. "Balanced Avoidance Games on Random Graphs." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AE,..., Proceedings (January 1, 2005). http://dx.doi.org/10.46298/dmtcs.3454.
Full textAbstract:
International audience We introduce and study balanced online graph avoidance games on the random graph process. The game is played by a player we call Painter. Edges of the complete graph with $n$ vertices are revealed two at a time in a random order. In each move, Painter immediately and irrevocably decides on a balanced coloring of the new edge pair: either the first edge is colored red and the second one blue or vice versa. His goal is to avoid a monochromatic copy of a given fixed graph $H$ in both colors for as long as possible. The game ends as soon as the first monochromatic copy of $H$ has appeared. We show that the duration of the game is determined by a threshold function $m_H = m_H(n)$. More precisely, Painter will asymptotically almost surely (a.a.s.) lose the game after $m = \omega (m_H)$ edge pairs in the process. On the other hand, there is an essentially optimal strategy, that is, if the game lasts for $m = o(m_H)$ moves, then Painter will a.a.s. successfully avoid monochromatic copies of H using this strategy. Our attempt is to determine the threshold function for certain graph-theoretic structures, e.g., cycles.
50
Schauz, Uwe. "Colorings and Nowhere-Zero Flows of Graphs in Terms of Berlekamp's Switching Game." Electronic Journal of Combinatorics 18, no. 1 (March 24, 2011). http://dx.doi.org/10.37236/552.
Full textAbstract:
We work with a unifying linear algebra formulation for nowhere-zero flows and colorings of graphs and matrices. Given a subspace (code) $U\leq{\mathbb{Z}_k^n}$ – e.g. the bond or the cycle space over ${\mathbb{Z}}_k$ of an oriented graph – we call a nowhere-zero tuple $f\in{\mathbb{Z}_k^n}$ a flow of $U$ if $f$ is orthogonal to $U$. In order to detect flows, we view the subspace $U$ as a light pattern on the $n$-dimensional Berlekamp Board ${\mathbb{Z}_k^n}$ with $k^n$ light bulbs. The lights corresponding to elements of $U$ are ON, the others are OFF. Then we allow axis-parallel switches of complete rows, columns, etc. The core result of this paper is that the subspace $U$ has a flow if and only if the light pattern $U$ cannot be switched off. In particular, a graph $G$ has a nowhere-zero $k$-flow if and only if the ${\mathbb{Z}}_k$-bond space of $G$ cannot be switched off. It has a vertex coloring with $k$ colors if and only if a certain corresponding code over ${\mathbb{Z}}_k$ cannot be switched off. Similar statements hold for Tait colorings, and for nowhere-zero points of matrices. Studying different normal forms to equivalence classes of light patterns, we find various new equivalents, e.g., for the Four Color Problem, Tutte's Flow Conjectures and Jaeger's Conjecture. Two of our equivalents for colorability and existence of nowhere zero flows of graphs include as special cases results by Matiyasevich, by Balázs Szegedy, and by Onn. Alon and Tarsi's sufficient condition for $k$-colorability also arrives, remarkably, as a generalized full equivalent.