To see the other types of publications on this topic, follow the link: N-part graph.
Journal articles on the topic 'N-part 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 'N-part 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
Day, Maxwell Christopher, Frank Christopher Hawthorne, and Ali Rostami. "Bond topology of chain, ribbon and tube silicates. Part II. Geometrical analysis of infinite 1D arrangements of (TO4) n− tetrahedra." Acta Crystallographica Section A Foundations and Advances 80, no. 3 (April 29, 2024): 258–81. http://dx.doi.org/10.1107/s2053273324002432.
Full textAbstract:
In Part I of this series, all topologically possible 1-periodic infinite graphs (chain graphs) representing chains of tetrahedra with up to 6–8 vertices (tetrahedra) per repeat unit were generated. This paper examines possible restraints on embedding these chain graphs into Euclidean space such that they are compatible with the metrics of chains of tetrahedra in observed crystal structures. Chain-silicate minerals with T = Si4+ (plus P5+, V5+, As5+, Al3+, Fe3+, B3+, Be2+, Zn2+ and Mg2+) have a grand nearest-neighbour 〈T–T〉 distance of 3.06±0.15 Å and a minimum T...T separation of 3.71 Å between non-nearest-neighbour tetrahedra, and in order for embedded chain graphs (called unit-distance graphs) to be possible atomic arrangements in crystals, they must conform to these metrics, a process termed equalization. It is shown that equalization of all acyclic chain graphs is possible in 2D and 3D, and that equalization of most cyclic chain graphs is possible in 3D but not necessarily in 2D. All unique ways in which non-isomorphic vertices may be moved are designated modes of geometric modification. If a mode (m) is applied to an equalized unit-distance graph such that a new geometrically distinct unit-distance graph is produced without changing the lengths of any edges, the mode is designated as valid (m v); if a new geometrically distinct unit-distance graph cannot be produced, the mode is invalid (m i). The parameters m v and m i are used to define ranges of rigidity of the unit-distance graphs, and are related to the edge-to-vertex ratio, e/n, of the parent chain graph. The program GraphT–T was developed to embed any chain graph into Euclidean space subject to the metric restraints on T–T and T...T. Embedding a selection of chain graphs with differing e/n ratios shows that the principal reason why many topologically possible chains cannot occur in crystal structures is due to violation of the requirement that T...T > 3.71 Å. Such a restraint becomes increasingly restrictive as e/n increases and indicates why chains with stoichiometry TO<2.5 do not occur in crystal structures.
2
Ghanbari, Nima, and Saeid Alikhani. "A graph related to the Euler ø function." Mathematical Gazette 107, no. 569 (July 2023): 263–72. http://dx.doi.org/10.1017/mag.2023.57.
Full textAbstract:
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph G is a pair G = (V, E), where V and E are the vertex set and the edge set of G, respectively. The order and size of G is the number of vertices and edges of G, respectively. The degree or valency of a vertex u in a graph G (loopless), denoted by deg (u), is the number of edges meeting at u. If, for every vertex ν in G, deg (ν) = k, we say that G is a k-regular graph. The cycle of order n is denoted by Cn and is a connected 2-regular graph. The path graph of order n is denoted by Pn and obtain by deleting an edge of Cn. A tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected undirected graph without cycle. A leaf (or pendant vertex) of a tree is a vertex of the tree of degree 1. An edge of a graph is said to be pendant if one of its vertices is a pendant vertex. A complete bipartite graph is a graph G with and such that every vertex of the set (part) X is connected to every vertex of the set (part) Y. If , then this graph is denoted by Km,n. The complete bipartite graph K1,n is called the star graph which has n + 1 vertices. The distance between two vertices u and ν of G, denoted by d (u, ν), is defined as the minimum number of edges of the walks between them. The complement of graph G is denoted by and is a graph with the same vertices such that two distinct vertices of are adjacent if, and only if, they are not adjacent in G. For more information on graphs, refer to [1].
3
LIN, YAW-LING, and STEVEN S. SKIENA. "COMPLEXITY ASPECTS OF VISIBILITY GRAPHS." International Journal of Computational Geometry & Applications 05, no. 03 (September 1995): 289–312. http://dx.doi.org/10.1142/s0218195995000179.
Full textAbstract:
In this paper, we consider two distinct problems related to complexity aspects of the visibility graphs of simple polygons. Recognizing visibility graphs is a long-standing open problem. It is not even known whether visibility graph recognition is in NP. That visibility graph recognition is in NP would be established if we could demonstrate that any n vertex visibility graph is realized by a polygon which can be drawn on an exponentially-sized grid. This motivates a study of the area requirements for realizing visibility graphs. In this paper, we prove: • Θ(n3) area is necessary and sufficient to realize the complete visibility graph Kn. • There exist visibility graphs which require exponential area to realize. • Any maximal outerplanar graph of diameter d can be realized in O(d2 · 2d) area, which can be as small as O(n log2 n) for a balanced mop. Linear maximal outer-planar graphs can be realized in O(n8) area. The second part of this paper considers the complexity of specific optimization problems on visibility graphs. Given a polygon P, we show that finding a maximum independent set, minimum vertex cover, or maximum dominating set in the visibility graph of P are all NP-complete. Further we show that for polygons P1 and P2, the problem of testing if they have isomorphic visibility graphs is isomorphism-complete. These problems remain hard when given the visibility graphs as input.
4
Xu, Chunyan, Rong Liu, Tong Zhang, Zhen Cui, Jian Yang, and Chunlong Hu. "Dual-Stream Structured Graph Convolution Network for Skeleton-Based Action Recognition." ACM Transactions on Multimedia Computing, Communications, and Applications 17, no. 4 (November 30, 2021): 1–22. http://dx.doi.org/10.1145/3450410.
Full textAbstract:
In this work, we propose a dual-stream structured graph convolution network ( DS-SGCN ) to solve the skeleton-based action recognition problem. The spatio-temporal coordinates and appearance contexts of the skeletal joints are jointly integrated into the graph convolution learning process on both the video and skeleton modalities. To effectively represent the skeletal graph of discrete joints, we create a structured graph convolution module specifically designed to encode partitioned body parts along with their dynamic interactions in the spatio-temporal sequence. In more detail, we build a set of structured intra-part graphs, each of which can be adopted to represent a distinctive body part (e.g., left arm, right leg, head). The inter-part graph is then constructed to model the dynamic interactions across different body parts; here each node corresponds to an intra-part graph built above, while an edge between two nodes is used to express these internal relationships of human movement. We implement the graph convolution learning on both intra- and inter-part graphs in order to obtain the inherent characteristics and dynamic interactions, respectively, of human action. After integrating the intra- and inter-levels of spatial context/coordinate cues, a convolution filtering process is conducted on time slices to capture these temporal dynamics of human motion. Finally, we fuse two streams of graph convolution responses in order to predict the category information of human action in an end-to-end fashion. Comprehensive experiments on five single/multi-modal benchmark datasets (including NTU RGB+D 60, NTU RGB+D 120, MSR-Daily 3D, N-UCLA, and HDM05) demonstrate that the proposed DS-SGCN framework achieves encouraging performance on the skeleton-based action recognition task.
5
Zhong, Chuang, and Shuangliang Tian. "Neighbor Sum Distinguishing Edge (Total) Coloring of Generalized Corona Product." Journal of Physics: Conference Series 2381, no. 1 (December 1, 2022): 012031. http://dx.doi.org/10.1088/1742-6596/2381/1/012031.
Full textAbstract:
Abstract The coloring theory of graphs is an important part of graph theory research. The key problem of the coloring theory of graphs is to determine the coloring number of each kind of coloring. Traditional coloring concepts mainly include proper vertex coloring, proper edge coloring, proper total coloring, and so on. In recent years, scholars at home and abroad have put forward some new coloring concepts, such as neighbor vertex distinguishing edge (total) coloring, and neighbor sum distinguishing edge (total) coloring, based on traditional coloring concepts and by adding other constraints. Some valuable results have been obtained, which further enrich the theory of graph coloring. For a proper [k]-edge coloring of a graph G, if for any adjacent vertex has a different sum of colors, then the coloring is a neighbor sum distinguishing [k]-edge coloring of G. For a proper [k]-total coloring of a graph G, if for any adjacent vertex has a different sum of colors, then the coloring is a neighbor sum distinguishing [k]-total coloring of G . In this paper, the coloring method and coloring index are determined by the process of induction and deduction and the construction of the dyeing method, and then the rationality of the method is verified by inverse proof and mathematical induction. If G is a simple graph with the order n ≥ 5 , and hn = (Hi ) i∈{1,2,…,n} is a sequence of disjoint simple graphs, where every Hi is a simple graph with the order m ≥ 7 . In this paper, we study the neighbor sum distinguishing edge(total) coloring of the generalized corona product G○hn of G and hn . The results are as follows: (1) If G is a path with order n , hn = (Hi ) i∈{1,2,…,n} is an alternating sequence of path and cycle with order m . If n is odd, we have χ Σ ′ ( G ∘ h n ) = m + 3 (2) If G is a path with order n , hn = (Hi ) i∈{1,2,…,n} is an alternating sequence of path and cycle with order m . If n is odd, we have χ Σ ′ ′ ( G ∘ h n ) = m + 4 Due to the late development of neighbor sum distinguishing edge (total) coloring of graphs, the related research results are relatively few. By studying the operation graph of a basic simple graph, we can provide the research basis and reference idea for the corresponding coloring of the general graph class. Therefore, it is of theoretical value to study the neighbor sum distinguishing edge (total) coloring problem of generalized corona products of graphs.
6
Sason, Igal. "Observations on graph invariants with the Lovász $ \vartheta $-function." AIMS Mathematics 9, no. 6 (2024): 15385–468. http://dx.doi.org/10.3934/math.2024747.
Full textAbstract:
<abstract><p>This paper delves into three research directions, leveraging the Lovász $ \vartheta $-function of a graph. First, it focuses on the Shannon capacity of graphs, providing new results that determine the capacity for two infinite subclasses of strongly regular graphs, and extending prior results. The second part explores cospectral and nonisomorphic graphs, drawing on a work by Berman and Hamud (2024), and it derives related properties of two types of joins of graphs. For every even integer such that $ n \geq 14 $, it is constructively proven that there exist connected, irregular, cospectral, and nonisomorphic graphs on $ n $ vertices, being jointly cospectral with respect to their adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, while also sharing identical independence, clique, and chromatic numbers, but being distinguished by their Lovász $ \vartheta $-functions. The third part focuses on establishing bounds on graph invariants, particularly emphasizing strongly regular graphs and triangle-free graphs, and compares the tightness of these bounds to existing ones. The paper derives spectral upper and lower bounds on the vector and strict vector chromatic numbers of regular graphs, providing sufficient conditions for the attainability of these bounds. Exact closed-form expressions for the vector and strict vector chromatic numbers are derived for all strongly regular graphs and for all graphs that are vertex- and edge-transitive, demonstrating that these two types of chromatic numbers coincide for every such graph. This work resolves a query regarding the variant of the $ \vartheta $-function by Schrijver and the identical function by McEliece <italic>et al.</italic> (1978). It shows, by a counterexample, that the $ \vartheta $-function variant by Schrijver does not possess the property of the Lovász $ \vartheta $-function of forming an upper bound on the Shannon capacity of a graph. This research paper also serves as a tutorial of mutual interest in zero-error information theory and algebraic graph theory.</p></abstract>
7
Petrenjuk, Volodymyr, and Dmytro Petreniuk. "Models of Klein Surface Obstruction Graphs." Cybernetics and Computer Technologies, no. 1 (March 29, 2024): 47–63. http://dx.doi.org/10.34229/2707-451x.24.1.4.
Full textAbstract:
The task of researching the structure of graphs of given connectivity, which are obstructions for a given surface of non-oriented kind, and building their models, from which obstruction graphs are formed by removing or compressing a set of edges, is considered. The issue of edge coverage of an obstruction graph of a given kind with a minimum number of quasi-stars with centers – planar graphs that have given sets of points and all edges are significant with respect to the reachability number 2 on the Euclidean plane and has reachability on the projective plane or Klein surface, is considered. K4, K2,3 or a degenerate graph. The task of researching the structure of graphs of undirected kind was considered [4–6]. In [7], the set of minors for the projective plane was compressed to 12 basic minors using the method of relative components, and a set of 62 minors of the Klein surface was constructed. To do this, we considered all non-isomorphic minimal embeddings of each of the basic minors and found the set of all different pairs of vertices that are reachable on the projective plane during the operations of removing or compressing an arbitrary edge of this graph to a point, then a pair of non-adjacent graph vertices was attached to the selected pair of points. In [8], the number of 2-connected obstruction graphs for the Klein surface was calculated, part of the diagrams of these graphs is given in [10]. Note that the following definition of the cell distance is similar to that in [11].Our approach, as a continuation of [9], will consist in finding the edge covering of an obstruction graph of a given kind by the minimum number of subgraphs of the covering from the number of quasi-stars with centers - graphs with essential edges relative to the number of reachability or nonorientable genus during compression to a point or removal operations edges relative to a given set of points with reachability number 2 relative to the Euclidean plane and reachable on projective planes or Klein surfaces, for example, these are subsets of the set of points of graphs K4, K2,3, K5\e, Kr, r >= 2, or graph-obstructions of the projective plane. We also found the necessary conditions for constructing obstruction graphs for the Klein surface by identifying pairs of center points and hanging vertices of three quasi-stars, thus we have the basis of an algorithm for constructing a larger number of obstruction graphs for the Klein surface. Hypothetically, a graph-obstruction of a given nonorientable genus has the form of a cylindrical surface with n, n >= 2, disks-bases and a side part, which can have common sets of points on the boundaries and on which are embedded, at least in part, the graph-centers of quasi-stars having a given set of reachability points 2 on the Euclidean plane, and on the side surface there are hanging edges that intersect on the plane and are inserted without crossing with the help of Mobius strips glued to the side surface. At the same time, the edges will have at least two nesting options in the side part of the cylindrical surface, but no more than the number of glued Mobius strips, thanks to which each hanging edge will nest on the Mobius strip, either with only one edge or with two adjacent edges. We have found the necessary conditions for constructing models of obstruction graphs for the Klein surface by identifying pairs of centers and hanging vertices of three quasi-stars, thus we have the basis of an algorithm for constructing a larger number of obstruction graphs for the Klein surface. The main result: statements 1, 2, 3 and the algorithm for constructing models of 3-connected graph-obstructions of the Klein surface. Keywords: φ-transformation of graphs, nonorientable surface, prototypes of graph-obstruction.
8
Ikhlaq, Hafiz Muhammad, Hafiz Muhammad Afzal Siddiqui, and Muhammad Imran. "A Comparative Study of Three Resolving Parameters of Graphs." Complexity 2021 (December 15, 2021): 1–13. http://dx.doi.org/10.1155/2021/1927181.
Full textAbstract:
Graph theory is one of those subjects that is a vital part of the digital world. It is used to monitor the movement of robots on a network, to debug computer networks, to develop algorithms, and to analyze the structural properties of chemical structures, among other things. It is also useful in airplane scheduling and the study of diffusion mechanisms. The parameters computed in this article are very useful in pattern recognition and image processing. A number d f , w = min d w , t , d w , s is referred as distance between f = t s an edge and w a vertex. d w , f 1 ≠ d w , f 2 implies that two edges f 1 , f 2 ∈ E are resolved by node w ∈ V . A set of nodes A is referred to as an edge metric generator if every two links/edges of Γ are resolved by some nodes of A and least cardinality of such sets is termed as edge metric dimension, e dim Γ for a graph Γ . A set B of some nodes of Γ is a mixed metric generator if any two members of V ∪ E are resolved by some members of B . Such a set B with least cardinality is termed as mixed metric dimension, m dim Γ . In this paper, the metric dimension, edge metric dimension, and mixed metric dimension of dragon graph T n , m , line graph of dragon graph L T n , m , paraline graph of dragon graph L S T n , m , and line graph of line graph of dragon graph L L T n , m have been computed. It is shown that these parameters are constant, and a comparative analysis is also given for the said families of graphs.
9
BEDNARSKA-BZDȨGA, MAŁGORZATA, DAN HEFETZ, MICHAEL KRIVELEVICH, and TOMASZ ŁUCZAK. "Manipulative Waiters with Probabilistic Intuition." Combinatorics, Probability and Computing 25, no. 6 (December 21, 2015): 823–49. http://dx.doi.org/10.1017/s0963548315000310.
Full textAbstract:
For positive integersnandqand a monotone graph property$\mathcal{A}$, we consider the two-player, perfect information game WC(n,q,$\mathcal{A}$), which is defined as follows. The game proceeds in rounds. In each round, the first player, called Waiter, offers the second player, called Client,q+ 1 edges of the complete graphKnwhich have not been offered previously. Client then chooses one of these edges which he keeps and the remainingqedges go back to Waiter. If, at the end of the game, the graph which consists of the edges chosen by Client satisfies the property$\mathcal{A}$, then Waiter is declared the winner; otherwise Client wins the game. In this paper we study such games (also known as Picker–Chooser games) for a variety of natural graph-theoretic parameters, such as the size of a largest component or the length of a longest cycle. In particular, we describe a phase transition type phenomenon which occurs when the parameterqis close tonand is reminiscent of phase transition phenomena in random graphs. Namely, we prove that ifq⩾ (1 + ϵ)n, then Client can avoid components of ordercϵ−2lnnfor some absolute constantc> 0, whereas forq⩽ (1 − ϵ)n, Waiter can force a giant, linearly sized component in Client's graph. In the second part of the paper, we prove that Waiter can force Client's graph to be pancyclic for everyq⩽cn, wherec> 0 is an appropriate constant. Note that this behaviour is in stark contrast to the threshold for pancyclicity and Hamiltonicity of random graphs.
10
Hamidi, Mohammad, and Irina Cristea. "Hyperideal-based zero-divisor graph of the general hyperring $ \mathbb{Z}_{n} $." AIMS Mathematics 9, no. 6 (2024): 15891–910. http://dx.doi.org/10.3934/math.2024768.
Full textAbstract:
<abstract><p>The aim of this paper is to introduce and study the concept of a hyperideal-based zero-divisor graph associated with a general hyperring. This is a generalized version of the zero-divisor graph associated with a commutative ring. For any general hyperring $ R $ having a hyperideal $ I $, the $ I $-based zero-divisor graph $ \Gamma^{(I)}(R) $ associated with $ R $ is the simple graph whose vertices are the elements of $ R\setminus I $ having their hyperproduct in $ I $, and two distinct vertices are joined by an edge when their hyperproduct has a non-empty intersection with $ I $. In the first part of the paper, we concentrate on some general properties of this graph related to absorbing elements, while the second part is dedicated to the study of the $ I $-based zero-divisor graph associated to the general hyperring $ \mathbb{Z}_n $ of the integers modulo $ n $, when $ n = 2p^mq $, with $ p $ and $ q $ two different odd primes, and fixing the hyperideal $ I $.</p></abstract>
11
Erdős, P., A. Hajnal, M. Simonovits, V. T. Sós, and E. Szemerédi. "Turán-Ramsey Theorems and Kp-Independence Numbers." Combinatorics, Probability and Computing 3, no. 3 (September 1994): 297–325. http://dx.doi.org/10.1017/s0963548300001218.
Full textAbstract:
Let the Kp-independence number αp (G) of a graph G be the maximum order of an induced subgraph in G that contains no Kp. (So K2-independence number is just the maximum size of an independent set.) For given integers r, p, m > 0 and graphs L1,…,Lr, we define the corresponding Turán-Ramsey function RTp(n, L1,…,Lr, m) to be the maximum number of edges in a graph Gn of order n such that αp(Gn) ≤ m and there is an edge-colouring of G with r colours such that the jth colour class contains no copy of Lj, for j = 1,…, r. In this continuation of [11] and [12], we will investigate the problem where, instead of α(Gn) = o(n), we assume (for some fixed p > 2) the stronger condition that αp(Gn) = o(n). The first part of the paper contains multicoloured Turán-Ramsey theorems for graphs Gn of order n with small Kp-independence number αp(Gn). Some structure theorems are given for the case αp(Gn) = o(n), showing that there are graphs with fairly simple structure that are within o(n2) of the extremal size; the structure is described in terms of the edge densities between certain sets of vertices.The second part of the paper is devoted to the case r = 1, i.e., to the problem of determining the asymptotic value offor p < q. Several results are proved, and some other problems and conjectures are stated.
12
NIKIFOROV, VLADIMIR. "A Spectral Erdős–Stone–Bollobás Theorem." Combinatorics, Probability and Computing 18, no. 3 (May 2009): 455–58. http://dx.doi.org/10.1017/s0963548309009687.
Full textAbstract:
Let r ≥ 3 and (c/rr)r log n ≥ 1. If G is a graph of order n and its largest eigenvalue μ(G) satisfies then G contains a complete r-partite subgraph with r − 1 parts of size ⌊(c/rr)r log n⌋ and one part of size greater than n1−cr−1.This result implies the Erdős–Stone–Bollobás theorem, the essential quantitative form of the Erdős–Stone theorem. Another easy consequence is that if F1, F2, . . . are r-chromatic graphs satisfying v(Fn) = o(log n), then
13
Qin, Chao, Yu Li, Zhongbi Wang, and Guiyun Chen. "Recognition of the symplectic simple group $ PSp_4(p) $ by the order and degree prime-power graph." AIMS Mathematics 9, no. 2 (2023): 2808–23. http://dx.doi.org/10.3934/math.2024139.
Full textAbstract:
<abstract><p>Let $ G $ be a finite group, $ \operatorname{cd}(G) $ the set of all irreducible character degrees of $ G $, and $ \rho(G) $ the set of all prime divisors of integers in $ \operatorname{cd}(G) $. For a prime $ p $ and a positive integer $ n $, let $ n_p $ denote the $ p $-part of $ n $. The degree prime-power graph of $ G $ is a graph whose vertex set is $ V(G) = \left\{p^{e_p(G)} \mid p \in \rho(G)\right\} $, where $ p^{e_p(G)} = \max \left\{n_p \mid n \in \operatorname{cd}(G)\right\} $, and there is an edge between distinct numbers $ x, y \in V(G) $ if $ x y $ divides some integer in $ \operatorname{cd}(G) $. The authors have previously shown that some non-abelian simple groups can be uniquely determined by their orders and degree prime-power graphs. In this paper, the authors build on this work and demonstrate that the symplectic simple group $ PSp_4(p) $ can be uniquely identified by its order and degree prime-power graph.</p></abstract>
14
Ferber, Asaf, Matthew Kwan, Bhargav Narayanan, Ashwin Sah, and Mehtaab Sawhney. "Friendly bisections of random graphs." Communications of the American Mathematical Society 2, no. 10 (December 20, 2022): 380–416. http://dx.doi.org/10.1090/cams/13.
Full textAbstract:
Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph G ( n , 1 / 2 ) \mathbb {G}(n,1/2) admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which n − o ( n ) n-o(n) vertices have more neighbours in their own part as across. Our proof is constructive, and in the process, we develop a new method to study stochastic processes driven by degree information in random graphs; this involves combining enumeration techniques with an abstract second moment argument.
15
Tao Zhang, Mike, Ken Goldberg, Gordon Smith, Robert-Paul Beretty, and Mark Overmars. "Pin design for part feeding." Robotica 19, no. 6 (September 2001): 695–702. http://dx.doi.org/10.1017/s0263574701003514.
Full textAbstract:
Industrial parts can be fed (oriented) using a sequence of fixed horizontal pins to topple the parts as they move past on a conveyor belt. We give an algorithm for designing a sequence of such pins for a given part. Given the n-sided convex polygonal projection of a part, its center of mass and frictional coefficients, our O(n2) algorithm computes the toppling graph, a new data structure that explicitly represents the mechanics of toppling, rolling, and jamming. We verify the toppling graph analysis with experiments. Our O(n3n) design algorithm uses the toppling graph to design a sequence of pin locations that will cause the part to emerge in a unique orientation or to determine that no such sequence exists.
16
MORRISON, SCOTT, DAVID PENNEYS, EMILY PETERS, and NOAH SNYDER. "SUBFACTORS OF INDEX LESS THAN 5, PART 2: TRIPLE POINTS." International Journal of Mathematics 23, no. 03 (March 2012): 1250016. http://dx.doi.org/10.1142/s0129167x11007586.
Full textAbstract:
We summarize the known obstructions to subfactors with principal graphs which begin with a triple point. One is based on Jones's quadratic tangles techniques, although we apply it in a novel way. The other two are based on connections techniques; one due to Ocneanu, and the other previously unpublished, although likely known to Haagerup.We then apply these obstructions to the classification of subfactors with index below 5. In particular, we eliminate three of the five families of possible principal graphs called "weeds" in the classification from S. Morrison and N. Snyder, Subfactors of index less than 5, part 1: the principal graph odometer, to appear in Comm. Math. Phys.
17
DING, GUOLI, and STAN DZIOBIAK. "Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs." Combinatorics, Probability and Computing 19, no. 4 (April 21, 2010): 579–91. http://dx.doi.org/10.1017/s0963548310000076.
Full textAbstract:
Thomas conjectured that there is an absolute constant c such that for every proper minor-closed class of graphs, there is a polynomial-time algorithm that can colour every G ∈ with at most χ(G) + c colours. We introduce a parameter ρ(), called the degenerate value of , which is defined to be the smallest r such that every G ∈ can be vertex-bipartitioned into a part of bounded tree-width (the bound depending only on ), and a part that is r-degenerate. Although the existence of one global bound for the degenerate values of all proper minor-closed classes would imply Thomas's conjecture, we prove that the values ρ() can be made arbitrarily large. The problem lies in the clique sum operation. As our main result, we show that excluding a planar graph with a fixed number of apex vertices gives rise to a minor-closed class with small degenerate value. As corollaries, we obtain that (i) the degenerate value of every class of graphs of bounded local tree-width is at most 6, and (ii) the degenerate value of the class of Kn-minor-free graphs is at most n + 1. These results give rise to P-time approximation algorithms for colouring any graph in these classes within an error of at most 7 and n + 2 of its chromatic number, respectively.
18
BEHBOODI, M., and Z. RAKEEI. "THE ANNIHILATING-IDEAL GRAPH OF COMMUTATIVE RINGS I." Journal of Algebra and Its Applications 10, no. 04 (August 2011): 727–39. http://dx.doi.org/10.1142/s0219498811004896.
Full textAbstract:
Let R be a commutative ring, with 𝔸(R) its set of ideals with nonzero annihilator. In this paper and its sequel, we introduce and investigate the annihilating-ideal graph of R, denoted by 𝔸𝔾(R). It is the (undirected) graph with vertices 𝔸(R)* ≔ 𝔸(R)\{(0)}, and two distinct vertices I and J are adjacent if and only if IJ = (0). First, we study some finiteness conditions of 𝔸𝔾(R). For instance, it is shown that if R is not a domain, then 𝔸𝔾(R) has ascending chain condition (respectively, descending chain condition) on vertices if and only if R is Noetherian (respectively, Artinian). Moreover, the set of vertices of 𝔸𝔾(R) and the set of nonzero proper ideals of R have the same cardinality when R is either an Artinian or a decomposable ring. This yields for a ring R, 𝔸𝔾(R) has n vertices (n ≥ 1) if and only if R has only n nonzero proper ideals. Next, we study the connectivity of 𝔸𝔾(R). It is shown that 𝔸𝔾(R) is a connected graph and diam (𝔸𝔾)(R) ≤ 3 and if 𝔸𝔾(R) contains a cycle, then gr (𝔸𝔾(R)) ≤ 4. Also, rings R for which the graph 𝔸𝔾(R) is complete or star, are characterized, as well as rings R for which every vertex of 𝔸𝔾(R) is a prime (or maximal) ideal. In Part II we shall study the diameter and coloring of annihilating-ideal graphs.
19
Chauhan, Ankit, Tobias Friedrich, and Ralf Rothenberger. "Greed is Good for Deterministic Scale-Free Networks." Algorithmica 82, no. 11 (June 19, 2020): 3338–89. http://dx.doi.org/10.1007/s00453-020-00729-z.
Full textAbstract:
Abstract Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach et al. (27th symposium on discrete algorithms (SODA), pp 1306–1325, 2016) introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks satisfy both properties and exploit them to design faster algorithms for a number of classical graph problems. We complement their work by showing that some well-studied random graph models exhibit both of the mentioned PLB properties. PLB-U and PLB-N hold with high probability for Chung–Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability or almost surely for those random graph classes. In the second part we study three classical $$\textsf {NP}$$ NP -hard optimization problems on PLB networks. It is known that on general graphs with maximum degree $$\Delta$$ Δ , a greedy algorithm, which chooses nodes in the order of their degree, only achieves a $$\Omega (\ln \Delta )$$ Ω ( ln Δ ) -approximation for Minimum Vertex Cover and Minimum Dominating Set, and a $$\Omega (\Delta )$$ Ω ( Δ ) -approximation for Maximum Independent Set. We prove that the PLB-U property with $$\beta >2$$ β > 2 suffices for the greedy approach to achieve a constant-factor approximation for all three problems. We also show that these problems are -hard even if PLB-U, PLB-N, and an additional power-law lower bound on the degree distribution hold. Hence, a PTAS cannot be expected unless = . Furthermore, we prove that all three problems are in if the PLB-U property holds.
20
Bodwin, Greg, and Virginia Vassilevska Williams. "Better Distance Preservers and Additive Spanners." ACM Transactions on Algorithms 17, no. 4 (October 31, 2021): 1–24. http://dx.doi.org/10.1145/3490147.
Full textAbstract:
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers , which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called consistency , stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that any p demand pairs in an n -node undirected unweighted graph have a distance preserver on O( n 2/3 p 2/3 + np 1/3 edges. We leave a conjecture that the right bound is O ( n 2/3 p 2/3 + n ) or better. The second part of this paper leverages these distance preservers in a new construction of additive spanners , which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners on O(n) edges with + O ( n 3/7 + ε ) error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii.
21
Bodwin, Greg, and Virginia Vassilevska Williams. "Better Distance Preservers and Additive Spanners." ACM Transactions on Algorithms 17, no. 4 (October 31, 2021): 1–24. http://dx.doi.org/10.1145/3490147.
Full textAbstract:
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers , which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called consistency , stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that any p demand pairs in an n -node undirected unweighted graph have a distance preserver on O( n 2/3 p 2/3 + np 1/3 edges. We leave a conjecture that the right bound is O ( n 2/3 p 2/3 + n ) or better. The second part of this paper leverages these distance preservers in a new construction of additive spanners , which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners on O(n) edges with + O ( n 3/7 + ε ) error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii.
22
HU, XIAOLAN, YUNQING ZHANG, and YAOJUN CHEN. "A NOTE ON ALMOST BALANCED BIPARTITIONS OF A GRAPH." Bulletin of the Australian Mathematical Society 91, no. 2 (October 14, 2014): 177–82. http://dx.doi.org/10.1017/s0004972714000781.
Full textAbstract:
AbstractLet $G$ be a graph of order $n\geq 6$ with minimum degree ${\it\delta}(G)\geq 4$. Arkin and Hassin [‘Graph partitions with minimum degree constraints’, Discrete Math. 190 (1998), 55–65] conjectured that there exists a bipartition $S,T$ of $V(G)$ such that $\lfloor n/2\rfloor -2\leq |S|,|T|\leq \lceil n/2\rceil +2$ and the minimum degrees in the subgraphs induced by $S$ and $T$ are at least two. In this paper, we first show that $G$ has a bipartition such that the minimum degree in each part is at least two, and then prove that the conjecture is true if the complement of $G$ contains no complete bipartite graph $K_{3,r}$, where $r=\lfloor n/2\rfloor -3$.
23
Gu, Mei-Mei, Hong-Xia Yan, and Jou-Ming Chang. "A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications." Mathematics 12, no. 2 (January 14, 2024): 268. http://dx.doi.org/10.3390/math12020268.
Full textAbstract:
“Linearly many faults” is a phenomenon observed by Cheng and Lipták in which a specific structure emerges when a graph is disconnected and often occurs in various interconnection networks. This phenomenon means that if a certain number of vertices or edges are deleted from a graph, the remaining part either stays connected or breaks into one large component along with smaller components with just a few vertices. This phenomenon can be observed in many types of graphs and has important implications for network analysis and optimization. In this paper, we first validate the phenomenon of linearly many faults for surviving graph of a burnt pancake graph BPn when removing any edge subset with a size of approximately six times λ(BPn). For graph G, the ℓ-component edge connectivity denoted as λℓ(G) (resp., the ℓ-extra edge connectivity denoted as λ(ℓ)(G)) is the cardinality of a minimum edge subset S such that G−S is disconnected and has at least ℓ components (resp., each component of G−S has at least ℓ+1 vertices). Both λℓ(G) and eλ(ℓ)(G) are essential metrics for network reliability assessment. Specifically, from the property of “linearly many faults”, we may further prove that λ5(BPn)=λ(3)(BPn)+3=4n−3 for n⩾5; λ6(BPn)=λ(4)(BPn)+4=5n−4 and λ7(BPn)=λ(5)(BPn)+5=6n−5 for n⩾6.
24
Koponen, Vera. "A Limit Law of Almost l-partite Graphs." Journal of Symbolic Logic 78, no. 3 (September 2013): 911–36. http://dx.doi.org/10.2178/jsl.7803110.
Full textAbstract:
AbstractFor integers l ≥ 1, d ≥ 0 we study (undirected) graphs with vertices 1, …, n such that the vertices can be partitioned into l parts such that every vertex has at most d neighbours in its own part. The set of all such graphs is denoted Pn (l, d). We prove a labelled first-order limit law, i.e., for every first-order sentence φ, the proportion of graphs in Pn (l, d) that satisfy φ converges as n → ∞. By combining this result with a result of Hundack, Prömel and Steger [12] we also prove that if 1 ≤ s1 ≤ … ≤ sl are integers, then Forb() has a labelled first-order limit law, where Forb() denotes the set of all graphs with vertices 1, …, n, for some n, in which there is no subgraph isomorphic to the complete (l + 1 )-partite graph with parts of sizes 1, s1, …, sl. In the course of doing this we also prove that there exists a first-order formula ξ, depending only on l and d, such that the proportion of ∈ Pn (l, d) with the following property approaches 1 as n → ∞: there is a unique partition of {1, …, n} into l parts such that every vertex has at most d neighbours in its own part, and this partition, viewed as an equivalence relation, is defined by ξ.
25
Ma, Xintao, Liyan Dong, Yuequn Wang, Yongli Li, and Hao Zhang. "MNI: An enhanced multi-task neighborhood interaction model for recommendation on knowledge graph." PLOS ONE 16, no. 10 (October 28, 2021): e0258410. http://dx.doi.org/10.1371/journal.pone.0258410.
Full textAbstract:
To alleviate the data sparsity and cold start problems for collaborative filtering in recommendation systems, side information is usually leveraged by researchers to improve the recommendation performance. The utility of knowledge graph regards the side information as part of the graph structure and gives an explanation for recommendation results. In this paper, we propose an enhanced multi-task neighborhood interaction (MNI) model for recommendation on knowledge graphs. MNI explores not only the user-item interaction but also the neighbor-neighbor interactions, capturing a more sophisticated local structure. Besides, the entities and relations are also semantically embedded. And with the cross&compress unit, items in the recommendation system and entities in the knowledge graph can share latent features, and thus high-order interactions can be investigated. Through extensive experiments on real-world datasets, we demonstrate that MNI outperforms some of the state-of-the-art baselines both for CTR prediction and top-N recommendation.
26
Vishnupriya, R., J. Suresh, S. Sivakumar, and R. Ranjith Kumar. "N—H...O and N—H...N interactions in three pyran derivatives." Acta Crystallographica Section C Crystal Structure Communications 69, no. 6 (May 2, 2013): 642–46. http://dx.doi.org/10.1107/s0108270113010676.
Full textAbstract:
The three pyran structures 6-methylamino-5-nitro-2,4-diphenyl-4H-pyran-3-carbonitrile, C19H15N3O3, (I), 4-(3-fluorophenyl)-6-methylamino-5-nitro-2-phenyl-4H-pyran-3-carbonitrile, C19H14FN3O3, (II), and 4-(4-chlorophenyl)-6-methylamino-5-nitro-2-phenyl-4H-pyran-3-carbonitrile, C19H14ClN3O3, (III), differ in the nature of the aryl group at the 4-position. The heterocyclic ring in all three structures adopts a flattened boat conformation. The dihedral angle between the pseudo-axial phenyl substituent and the flat part of the pyran ring is 89.97 (1)° in (I), 80.11 (1)° in (II) and 87.77 (1)° in (III). In all three crystal structures, a strong intramolecular N—H...O hydrogen bond links the flat conjugated H—N—C=C—N—O fragment into a six-membered ring. In (II), molecules are linked into dimeric aggregates by N—H... O(nitro) hydrogen bonds, generating anR22(12) graph-set motif. In (III), intermolecular N—H...N and C—H...N hydrogen bonds link the molecules into a linear chain pattern generatingC(8) andC(9) graph-set motifs, respectively.
27
Povh, Janez. "On the Embed and Project Algorithm for the Graph Bandwidth Problem." Mathematics 9, no. 17 (August 24, 2021): 2030. http://dx.doi.org/10.3390/math9172030.
Full textAbstract:
The graph bandwidth problem, where one looks for a labeling of graph vertices that gives the minimum difference between the labels over all edges, is a classical NP-hard problem that has drawn a lot of attention in recent decades. In this paper, we focus on the so-called Embed and Project Algorithm (EPA) introduced by Blum et al. in 2000, which in the main part has to solve a semidefinite programming relaxation with exponentially many linear constraints. We present several theoretical properties of this special semidefinite programming problem (SDP) and a cutting-plane-like algorithm to solve it, which works very efficiently in combination with interior-point methods or with the bundle method. Extensive numerical results demonstrate that this algorithm, which has only been studied theoretically so far, in practice gives very good labeling for graphs with n≤1000.
28
Planat, M., and M. Saniga. "On the Pauli graphs on N-qudits." Quantum Information and Computation 8, no. 1&2 (January 2008): 127–46. http://dx.doi.org/10.26421/qic8.1-2-9.
Full textAbstract:
A comprehensive graph theoretical and finite geometrical study of the commutation relations between the generalized Pauli operators of $N$-qudits is performed in which vertices/points correspond to the operators and edges/lines join commuting pairs of them. As per two-qubits, all basic properties and partitionings of the corresponding {\it Pauli graph} are embodied in the geometry of the generalized quadrangle of order two. Here, one identifies the operators with the points of the quadrangle and groups of maximally commuting subsets of the operators with the lines of the quadrangle. The three basic partitionings are (a) a pencil of lines and a cube, (b) a Mermin's array and a bipartite-part and (c) a maximum independent set and the Petersen graph. These factorizations stem naturally from the existence of three distinct geometric hyperplanes of the quadrangle, namely a set of points collinear with a given point, a grid and an ovoid, which answer to three distinguished subsets of the Pauli graph, namely a set of six operators commuting with a given one, a Mermin's square, and set of five mutually non-commuting operators, respectively. The generalized Pauli graph for multiple qubits is found to follow from symplectic polar spaces of order two, where maximal totally isotropic subspaces stand for maximal subsets of mutually commuting operators. The substructure of the (strongly regular) $N$-qubit Pauli graph is shown to be pseudo-geometric, i.\,e., isomorphic to a graph of a partial geometry. Finally, the (not strongly regular) Pauli graph of a two-qutrit system is introduced; here it turns out more convenient to deal with its dual in order to see all the parallels with the two-qubit case and its surmised relation with the generalized quadrangle $Q(4,3)$, the dual of $W(3)$.
29
McMains, Sara, and Xiaorui Chen. "Finding Undercut-Free Parting Directions for Polygons with Curved Edges." Journal of Computing and Information Science in Engineering 6, no. 1 (October 12, 2005): 60–68. http://dx.doi.org/10.1115/1.2164450.
Full textAbstract:
We consider the problem of whether a given geometry can be molded in a two-part, rigid, reusable mold with opposite removal directions. We describe an efficient algorithm for solving the opposite direction moldability problem for a 2D “polygon” bounded by edges that may be either straight or curved. We introduce a structure, the normal graph of the polygon, that represents the range of normals of the polygon’s edges, along with their connectivity. We prove that the normal graph captures the directions of all lines corresponding to feasible parting directions. Rather than building the full normal graph, which could take time O(nlogn) for a polygon bounded by n possibly curved edges, we build a summary structure in O(n) time and space, from which we can determine all feasible parting directions in time O(n).
30
Marx, Dániel, and Michał Pilipczuk. "Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams." ACM Transactions on Algorithms 18, no. 2 (April 30, 2022): 1–64. http://dx.doi.org/10.1145/3483425.
Full textAbstract:
We study a general family of facility location problems defined on planar graphs and on the two-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the n O (√ k ) time brute force algorithm of selecting k objects can be improved to n O (√ k ) time. The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. We focus on the Voronoi diagram of a hypothetical solution of k objects, guess a balanced separator cycle of this Voronoi diagram to obtain a set that separates the solution in a balanced way, and then recurse on the resulting subproblems. The following list is an exemplary selection of concrete consequences of our main result. We can solve each of the following problems in time n O (√ k ), where n is the total size of the input: d -Scattered Set : find k vertices in an edge-weighted planar graph that pairwise are at distance at least d from each other ( d is part of the input). d -Dominating Set (or ( k,d )-Center): find k vertices in an edge-weighted planar graph such that every vertex of the graph is at distance at most d from at least one selected vertex ( d is part of the input). Given a set D of connected vertex sets in a planar graph G , find k disjoint vertex sets in D . Given a set D of disks in the plane (of possibly different radii), find k disjoint disks in D . Given a set D of simple polygons in the plane, find k disjoint polygons in D . Given a set D of disks in the plane (of possibly different radii) and a set P of points, find k disks in D that together cover the maximum number of points in P . Given a set D of axis-parallel squares in the plane (of possibly different sizes) and a set P of points, find k squares in D that together cover the maximum number of points in P . It is known from previous work that, assuming the Exponential Time Hypothesis (ETH), there is no f ( k ) n o (√ k ) time algorithm for any computable function f for any of these problems. Furthermore, we give evidence that packing problems have n O (√ k ) time algorithms for a much more general class of objects than covering problems have. For example, we show that, assuming ETH, the problem where a set D of axis-parallel rectangles and a set P of points are given, and the task is to select k rectangles that together cover the entire point set, does not admit an f ( k ) n o ( k ) time algorithm for any computable function f .
31
González A, G., and R. Galindo. "Steady state determination using bond graphs for systems with singular state matrix." Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering 225, no. 7 (August 26, 2011): 887–901. http://dx.doi.org/10.1177/2041304110394552.
Full textAbstract:
A bond graph procedure to get the steady state value for linear time-invariant systems is presented. The general case of a singular state matrix is considered. The procedure is based on a junction structure configuration with derivative causality assignment, and on relationships of the bond graphs with integral and derivative causality assignments. It is shown that the structurally null modes, i.e. the poles at the origin, are cancelled for steady state. The key to cancel the poles at the origin is that the adjugate matrix of sIn − Ap multiplies Bp yielding the zeros at the origin with the same order that the structurally null modes, where ( Ap, Bp, Cp, Dp) is a state space realization of a linear time-invariant system, s is the Laplace operator and In, is an n × n identity matrix. Hence, this unstable part of the system is cancelled and the steady state can be obtained. Thus, the singularity of the state space matrix is avoided, and the steady state is obtained from the bond graph with derivative causality assignment. Since the singular state matrix is considered, it is shown that by using the bond graph with derivative causality assignment, an equivalent system with linearly independent state variables can be obtained. An example of an electrical system with an electrical transformer modelled by an I-field whose state matrix is singular is presented. Also, the proposed methodology for a load driven by two DC motors is applied.
32
Marjai, Péter, Bence Szabari, and Attila Kiss. "An Experimental Study on Centrality Measures Using Clustering." Computers 10, no. 9 (September 15, 2021): 115. http://dx.doi.org/10.3390/computers10090115.
Full textAbstract:
Graphs can be found in almost every part of modern life: social networks, road networks, biology, and so on. Finding the most important node is a vital issue. Up to this date, numerous centrality measures were proposed to address this problem; however, each has its drawbacks, for example, not scaling well on large graphs. In this paper, we investigate the ranking efficiency and the execution time of a method that uses graph clustering to reduce the time that is needed to define the vital nodes. With graph clustering, the neighboring nodes representing communities are selected into groups. These groups are then used to create subgraphs from the original graph, which are smaller and easier to measure. To classify the efficiency, we investigate different aspects of accuracy. First, we compare the top 10 nodes that resulted from the original closeness and betweenness methods with the nodes that resulted from the use of this method. Then, we examine what percentage of the first n nodes are equal between the original and the clustered ranking. Centrality measures also assign a value to each node, so lastly we investigate the sum of the centrality values of the top n nodes. We also evaluate the runtime of the investigated method, and the original measures in plain implementation, with the use of a graph database. Based on our experiments, our method greatly reduces the time consumption of the investigated centrality measures, especially in the case of the Louvain algorithm. The first experiment regarding the accuracy yielded that the examination of the top 10 nodes is not good enough to properly evaluate the precision. The second experiment showed that the investigated algorithm in par with the Paris algorithm has around 45–60% accuracy in the case of betweenness centrality. On the other hand, the last experiment resulted that the investigated method has great accuracy in the case of closeness centrality especially in the case of Louvain clustering algorithm.
33
Devillers, Raymond, and Ronny Tredup. "Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues." Fundamenta Informaticae 187, no. 2-4 (October 19, 2022): 139–65. http://dx.doi.org/10.3233/fi-222135.
Full textAbstract:
Petri net synthesis consists in deciding for a given transition system A whether there exists a Petri net N whose reachability graph is isomorphic to A. Several works examined the synthesis of Petri net subclasses that restrict, for every place p of the net, the cardinality of its preset or of its postset or both in advance by small natural numbers ϱ and κ, respectively, such as for example (weighted) marked graphs, (weighted) T-systems and choice-free nets. In this paper, we study the synthesis aiming at Petri nets which have such restricted place environments, from the viewpoint of classical and parameterized complexity: We first show that, for any fixed natural numbers ϱ and κ, deciding whether for a given transition system A there is a Petri net N such that (1) its reachability graph is isomorphic to A and (2) for every place p of N the preset of p has at most ϱ and the postset of p has at most κ elements is doable in polynomial time. Secondly, we introduce a modified version of the problem, namely ENVIRONMENT RESTRICTED SYNTHESIS (ERS, for short), where ϱ and κ are part of the input, and show that ERS is NPcomplete, regardless whether the sought net is impure or pure. In case of the impure nets, our methods also imply that ERS parameterized by ϱ + κ is W[2]-hard.
34
Bringmann, Karl, Marvin KüNnemann, and André Nusser. "Discrete Fréchet Distance under Translation." ACM Transactions on Algorithms 17, no. 3 (August 2021): 1–42. http://dx.doi.org/10.1145/3460656.
Full textAbstract:
The discrete Fréchet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fréchet distance under translation, which enables detection of similar movement patterns in different spatial domains. For polygonal curves of length n in the plane, the fastest known algorithm runs in time Õ( n 5 ) [12]. This is achieved by constructing an arrangement of disks of size Õ( n 4 ), and then traversing its faces while updating reachability in a directed grid graph of size N := Õ( n 5 ), which can be done in time Õ(√ N ) per update [27]. The contribution of this article is two-fold. First, although it is an open problem to solve dynamic reachability in directed grid graphs faster than Õ(√ N ), we improve this part of the algorithm: We observe that an offline variant of dynamic s - t -reachability in directed grid graphs suffices, and we solve this variant in amortized time Õ( N 1/3 ) per update, resulting in an improved running time of Õ( N 4.66 ) for the discrete Fréchet distance under translation. Second, we provide evidence that constructing the arrangement of size Õ( N 4 ) is necessary in the worst case by proving a conditional lower bound of n 4 - o(1) on the running time for the discrete Fréchet distance under translation, assuming the Strong Exponential Time Hypothesis.
35
Potůček, Radovan. "The Number of Fillings a 2×2×n prism with 1×1×2 prisms." EQUATIONS 3 (October 3, 2023): 104–14. http://dx.doi.org/10.37394/232021.2023.3.12.
Full textAbstract:
This paper is inspired by very interesting YouTube video of Burkard Polster, professor of mathematics at Monash University in Melbourne, Australia, which, among other things, concerned the number of ways to fill a part of the plane with dominoes, i.e. 1×2 rectangles. First we deal with the numbers of fillings the 2×2×n prism with elementary 1×1×2 prisms for n=1,2,3,4,5. Special symbolism and figures showing the filling of the prism are used as well as the concept of matching from graph theory and the corresponding graph diagrams. Then we generalize these specific considerations and derive a general recurrence formula for any n≥3, which expresses the number of fillings of the 2×2×n prism with 1×1×2 elementary prisms, which in a way can be considered as spatial domino cubes, if we do not consider their marking with pairs of numbers from 0 to 6.
36
CHAUDHURI, SUTAPA. "CHAOTIC GRAPH THEORY APPROACH FOR IDENTIFICATION OF CONVECTIVE AVAILABLE POTENTIAL ENERGY (CAPE) PATTERNS REQUIRED FOR THE GENESIS OF SEVERE THUNDERSTORMS." Advances in Complex Systems 10, no. 03 (September 2007): 413–22. http://dx.doi.org/10.1142/s0219525907001215.
Full textAbstract:
Severe thunderstorms are a manifestation of deep convection. Conditional instability is known to be the mechanism by which thunderstorms are formed. The energy that drives conditional instability is convective available potential energy (CAPE), which is computed with radio sonde data at each pressure level. The purpose of the present paper is to identify the pattern or shape of CAPE required for the genesis of severe thunderstorms over Kolkata (22°32′N, 88°20′E) confined within the northeastern part (20°N to 24°N latitude, 85°E to 93°E longitude) of India. The method of chaotic graph theory is adopted for this purpose. Chaotic graphs of pressure levels and CAPE are formed for thunderstorm and non-thunderstorm days. Ranks of the adjacency matrices constituted with the union of chaotic graphs of pressure levels and CAPE are computed for thunderstorm and non-thunderstorm days. The results reveal that the rank of the adjacency matrix is maximum for non-thunderstorm days and a column with all zeros occurs very quickly on severe thunderstorms days. This indicates that CAPE loses connectivity with pressure levels very early on severe thunderstorm days, showing that for the genesis of severe thunderstorms over Kolkata short, and therefore broad, CAPE is preferred.
37
Nichol, Gary S., Jamie M. Frost, Sergio Sanz, and Euan K. Brechin. "Crystal structure of 2-hydroxy-N-(2-hydroxyethyl)-N-{2-hydroxy-3-[(E)-N-hydroxyethanimidoyl]-5-methylbenzyl}ethanaminium acetate monohydrate." Acta Crystallographica Section E Crystallographic Communications 71, no. 3 (February 18, 2015): o186—o187. http://dx.doi.org/10.1107/s2056989015002418.
Full textAbstract:
The structure of the title hydrated molecular salt, C14H23N2O4+·C2H3O2−·H2O, was determined as part of a wider study on the use of the molecule as a polydentate ligand in the synthesis of MnIIIclusters with magnetic properties. The cation features intramolecular O—H...N and N—H...O hydrogen-bond interactions. The crystal structure features a range of intermolecular hydrogen-bonding interactions, principally O—H...O interactions between all three species in the asymmetric unit. AnR24(8) graph-set hydrogen-bonding motif between the anion and water molecules serves as a unit which links to the cationviathe diethanolamine group. Each O atom of the acetate anion accepts two hydrogen bonds.
38
Ganesan, Ghurumuruhan. "Infection Spread in Random Geometric Graphs." Advances in Applied Probability 47, no. 01 (March 2015): 164–81. http://dx.doi.org/10.1017/s0001867800007758.
Full textAbstract:
In this paper we study the speed of infection spread and the survival of the contact process in the random geometric graph G = G(n, r n , f) of n nodes independently distributed in S = [-½, ½]2 according to a certain density f(·). In the first part of the paper we assume that infection spreads from one node to another at unit rate and that infected nodes stay in the same state forever. We provide an explicit lower bound on the speed of infection spread and prove that infection spreads in G with speed at least D 1 nr n 2. In the second part of the paper we consider the contact process ξ t on G where infection spreads at rate λ > 0 from one node to another and each node independently recovers at unit rate. We prove that, for every λ > 0, with high probability, the contact process on G survives for an exponentially long time; there exist positive constants c 1 and c 2 such that, with probability at least 1 - c 1 / n 4, the contact process starting with all nodes infected survives up to time t n = exp(c 2 n/logn) for all n.
39
MATIGNON, DANIEL. "COMBINATORICS AND FOUR BRIDGED KNOTS." Journal of Knot Theory and Its Ramifications 10, no. 04 (June 2001): 493–527. http://dx.doi.org/10.1142/s0218216501000974.
Full textAbstract:
The ℝ P 3-Conjecture states a non-trivial knot in S 3 cannot yield ℝ P 3 by a Dehn surgery. Generically, in the knot-space S3-N(K), the intersection of a projective plane ℝP2 in ℝ P 3, and any 2-sphere S2 in S3 pierced by K, is a 1-complex which can be viewed as a graph in either the projective plane or the 2-sphere. Gordon and Luecke have used similar graphs arising as the intersection of two 2-spheres, to prove that a knot in S3 is determined by its complement. A part of this paper concerns some new combinatorial results on these graphs. They are considered as an unavoidable step towards showing that the ℝ P 3-Conjecture is true. Moreover, we use these results to prove that any non-trivial knot that could yield ℝ P 3 has at least five bridges.
40
Li, Shiqiao, and Jami J. Shah. "Recognition of User-Defined Turning Features for Mill/Turn Parts." Journal of Computing and Information Science in Engineering 7, no. 3 (July 6, 2007): 225–35. http://dx.doi.org/10.1115/1.2767256.
Full textAbstract:
This paper focuses on efficient algorithms for automatic recognition of user-defined turning features on mill/turn parts. As with other domains, recognition of interacting features is a difficult issue because feature interaction removes faces and alters the topology of the isolated turning features. This paper presents a method for efficiently recognizing both noninteracting and interacting rotational features from CAD model of mill/turn parts. Additionally, the method supports user-defined turning features that are represented using N-REP, a neutral feature representation language. First, the profiles of the revolved faces on a mill/turn part are obtained and the unturnable portions of these profiles are detected. These profiles then are used to construct the part graph and to solve feature interactions between coaxial turning features. Finally, graph-based and rule-based feature recognition are combined to recognize user-defined features.
41
Shekhawat, Krishnendra, and José P. Duarte. "Introduction to generic rectangular floor plans." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 32, no. 3 (May 30, 2018): 331–50. http://dx.doi.org/10.1017/s0890060417000671.
Full textAbstract:
AbstractAn important task in the initial stages of most architectural design processes is the design of planar floor plans, that are composed of non-overlapping rooms divided from each other by walls while satisfying given topological and dimensional constraints. The work described in this paper is part of a larger research aimed at developing the mathematical theory for examining the feasibility of given topological constraints and providing a generic floor plan solution for all possible design briefs.In this paper, we mathematically describe universal (or generic) rectangular floor plans with n rooms, that is, the floor plans that topologically contain all possible rectangular floor plans with n rooms. Then, we present a graph-theoretical approach for enumerating generic rectangular floor plans upto nine rooms. At the end, we demonstrate the transformation of generic floor plans into a floor plan corresponding to a given graph.
42
LETZTER, SHOHAM. "Path Ramsey Number for Random Graphs." Combinatorics, Probability and Computing 25, no. 4 (December 7, 2015): 612–22. http://dx.doi.org/10.1017/s0963548315000279.
Full textAbstract:
Answering a question raised by Dudek and Prałat, we show that if pn → ∞, w.h.p., whenever G = G(n, p) is 2-edge-coloured there is a monochromatic path of length (2/3 + o(1))n. This result is optimal in the sense that 2/3 cannot be replaced by a larger constant.As part of the proof we obtain the following result. Given a graph G on n vertices with at least $(1-\varepsilon)\binom{n}{2}$ edges, whenever G is 2-edge-coloured, there is a monochromatic path of length at least $(2/3 - 110\sqrt{\varepsilon})n$. This is an extension of the classical result by Gerencsér and Gyárfás which says that whenever Kn is 2-coloured there is a monochromatic path of length at least 2n/3.
43
Hu, Zhichao, Likun Liu, Haining Yu, and Xiangzhan Yu. "Using Graph Representation in Host-Based Intrusion Detection." Security and Communication Networks 2021 (December 7, 2021): 1–13. http://dx.doi.org/10.1155/2021/6291276.
Full textAbstract:
Cybersecurity has become an important part of our daily lives. As an important part, there are many researches on intrusion detection based on host system call in recent years. Compared to sentences, a sequence of system calls has unique characteristics. It contains implicit pattern relationships that are less sensitive to the order of occurrence and that have less impact on the classification results when the frequency of system calls varies slightly. There are also various properties such as resource consumption, execution time, predefined rules, and empirical weights of system calls. Commonly used word embedding methods, such as Bow, TI-IDF, N-Gram, and Word2Vec, do not fully exploit such relationships in sequences as well as conveniently support attribute expansion. To solve these problems, we introduce Graph Representation based Intrusion Detection (GRID), an intrusion detection framework based on graph representation learning. It captures the potential relationships between system calls to learn better features, and it is applicable to a wide range of back-end classifiers. GRID utilizes a new sequence embedding method Graph Random State Embedding (GRSE) that uses graph structures to model a finite number of sequence items and represent the structural association relationships between them. A more efficient representation of sequence embeddings is generated by random walks, word embeddings, and graph pooling. Moreover, it can be easily extended to sequences with attributes. Our experimental results on the AFDA-LD dataset show that GRID has an average improvement of 2% using the GRSE embedding method comparing to others.
44
Mufti, Zeeshan Saleem, Rukhshanda Anjum, Fairouz Tchier, Hafsa Sajid, Qin Xin, and Faria Ahmed Shami. "Topological Study of Zirconium Tetrachloride Z r C l 4 under Molecular Descriptors." Mathematical Problems in Engineering 2022 (April 22, 2022): 1–9. http://dx.doi.org/10.1155/2022/3105317.
Full textAbstract:
Topological index is a numerical parameter which characterizes the topology of the molecular structure. Topological indices are a very prominent part of the study of chemical structures in which properties of organic or inorganic compounds are under observation and calculated such as physical properties, chemical reactivity, or biological activity. Most of the topological indices of molecular graph-based structure which depends on vertex degrees have been visualized. In this study, we compute some degree-based topological indices of zirconium tetrachloride Z n C l 4 m , n .
45
Colarte-Gómez, Liena, Laura Costa, Simone Marchesi, Rosa M. Miró-Roig, and Marti Salat-Moltó. "Hypertetrahedral arrangements." Mathematische Zeitschrift 301, no. 1 (December 19, 2021): 515–39. http://dx.doi.org/10.1007/s00209-021-02911-7.
Full textAbstract:
AbstractIn this paper, we introduce the notion of a complete hypertetrahedral arrangement $${\mathcal {A}}$$ A in $${\mathbb {P}}^{n}$$ P n . We address two basic problems. First, we describe the local freeness of $${\mathcal {A}}$$ A in terms of smaller complete hypertetrahedral arrangements and graph theory properties, specializing the Mustaţă–Schenck criterion. As an application, we obtain that general complete hypertetrahedral arrangements are not locally free. In the second part of this paper, we bound the initial degree of the first syzygy module of the Jacobian ideal of $${\mathcal {A}}$$ A .
46
Horiyama, Takashi, Yasuaki Kobayashi, Hirotaka Ono, Kazuhisa Seto, and Ryu Suzuki. "Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 18 (March 24, 2024): 20726–34. http://dx.doi.org/10.1609/aaai.v38i18.30060.
Full textAbstract:
The uniqueness of an optimal solution to a combinatorial optimization problem attracts many fields of researchers' attention because it has a wide range of applications, it is related to important classes in computational complexity, and the existence of only one solution is often critical for algorithm designs in theory. However, as the authors know, there is no major benchmark set consisting of only instances with unique solutions, and no algorithm generating instances with unique solutions is known; a systematic approach to getting a problem instance guaranteed having a unique solution would be helpful. A possible approach is as follows: Given a problem instance, we specify a small part of a solution in advance so that only one optimal solution meets the specification. This paper formulates such a ``pre-assignment'' approach for the vertex cover problem as a typical combinatorial optimization problem and discusses its computational complexity. First, we show that the problem is ΣP2-complete in general, while the problem becomes NP-complete when an input graph is bipartite. We then present an O(2.1996^n)-time algorithm for general graphs and an O(1.9181^n)-time algorithm for bipartite graphs, where n is the number of vertices. The latter is based on an FPT algorithm with O*(3.6791^τ) time for vertex cover number τ. Furthermore, we show that the problem for trees can be solved in O(1.4143^n) time.
47
ASANO, TETSUO, LEONIDAS J. GUIBAS, and TAKESHI TOKUYAMA. "WALKING IN AN ARRANGEMENT TOPOLOGICALLY." International Journal of Computational Geometry & Applications 04, no. 02 (June 1994): 123–51. http://dx.doi.org/10.1142/s0218195994000094.
Full textAbstract:
We present topological walk, an on-line algorithm for computing a walk in an arrangement. Here, a walk is a visit to the cells of an arrangement in an order such that consecutive cells are adjacent to each other. The algorithm can walk in a part of an arrangement efficiently; more precisely, given an arrangement of n lines in a convex region containing K cells, a walk is performed in O(K + n log n) time and O(n) working space. Several optimal-cell-finding problems can be solved efficiently applying the topological walk. Further, a construction of a spanning tree with maximum node degree three of the dual graph of an arrangement is given.
48
Ganesan, Ghurumuruhan. "Infection Spread in Random Geometric Graphs." Advances in Applied Probability 47, no. 1 (March 2015): 164–81. http://dx.doi.org/10.1239/aap/1427814586.
Full textAbstract:
In this paper we study the speed of infection spread and the survival of the contact process in the random geometric graph G = G(n, rn, f) of n nodes independently distributed in S = [-½, ½]2 according to a certain density f(·). In the first part of the paper we assume that infection spreads from one node to another at unit rate and that infected nodes stay in the same state forever. We provide an explicit lower bound on the speed of infection spread and prove that infection spreads in G with speed at least D1nrn2. In the second part of the paper we consider the contact process ξt on G where infection spreads at rate λ > 0 from one node to another and each node independently recovers at unit rate. We prove that, for every λ > 0, with high probability, the contact process on G survives for an exponentially long time; there exist positive constants c1 and c2 such that, with probability at least 1 - c1 / n4, the contact process starting with all nodes infected survives up to time tn = exp(c2n/logn) for all n.
49
Yin, Jian-Hua, and Liang Zhang. "Solutions to problems about potentially K s,t -bigraphic pair." Open Mathematics 20, no. 1 (January 1, 2022): 460–64. http://dx.doi.org/10.1515/math-2022-0022.
Full textAbstract:
Abstract Let S = ( a 1 , … , a m ; b 1 , … , b n ) S=\left({a}_{1},\ldots ,{a}_{m};\hspace{0.33em}{b}_{1},\ldots ,{b}_{n}) , where a 1 , … , a m {a}_{1},\ldots ,{a}_{m} and b 1 , … , b n {b}_{1},\ldots ,{b}_{n} are two nonincreasing sequences of nonnegative integers. The pair S = ( a 1 , … , a m ; b 1 , … , b n ) S=\left({a}_{1},\ldots ,{a}_{m};\hspace{0.33em}{b}_{1},\ldots ,{b}_{n}) is said to be a bigraphic pair if there is a simple bipartite graph G = ( X ∪ Y , E ) G=\left(X\cup Y,E) such that a 1 , … , a m {a}_{1},\ldots ,{a}_{m} and b 1 , … , b n {b}_{1},\ldots ,{b}_{n} are the degrees of the vertices in X X and Y Y , respectively. In this case, G G is referred to as a realization of S S . Given a bigraphic pair S S , and a complete bipartite graph K s , t {K}_{s,t} , we say that S S is a potentially K s , t {K}_{s,t} -bigraphic pair if some realization of S S contains K s , t {K}_{s,t} as a subgraph (with s s vertices in the part of size m m and t t in the part of size n n ). Ferrara et al. (Potentially H-bigraphic sequences, Discuss. Math. Graph Theory 29 (2009), 583–596) defined σ ( K s , t , m , n ) \sigma \left({K}_{s,t},m,n) to be the minimum integer k k such that every bigraphic pair S = ( a 1 , … , a m ; b 1 , … , b n ) S=\left({a}_{1},\ldots ,{a}_{m};{b}_{1},\ldots ,{b}_{n}) with σ ( S ) = a 1 + ⋯ + a m ≥ k \sigma \left(S)={a}_{1}+\cdots +{a}_{m}\ge k is a potentially K s , t {K}_{s,t} -bigraphic pair. This problem can be viewed as a “potential” degree sequence relaxation of the (forcible) Turán problem. Ferrara et al. determined σ ( K s , t , m , n ) \sigma \left({K}_{s,t},m,n) for n ≥ m ≥ 9 s 4 t 4 n\ge m\ge 9{s}^{4}{t}^{4} . In this paper, we further determine σ ( K s , t , m , n ) \sigma \left({K}_{s,t},m,n) for n ≥ m ≥ s n\ge m\ge s and n + m ≥ 2 t 2 + t + s n+m\ge 2{t}^{2}+t+s . As two corollaries, if n ≥ m ≥ t 2 + t + s 2 n\ge m\ge {t}^{2}+\frac{t+s}{2} or if n ≥ m ≥ s n\ge m\ge s and n ≥ 2 t 2 + t n\ge 2{t}^{2}+t , the values σ ( K s , t , m , n ) \sigma \left({K}_{s,t},m,n) are determined completely. These results give a solution to a problem due to Ferrara et al. and a solution to a problem due to Yin and Wang.
50
Amely Jumaat, Siti, Ammar Syahmi Bin Mohd Anuar, Mohd Noor Abdullah, Nur Hanis Radzi, Rohaiza Hamdan, Suriana Salimin, and Muhammad Nafis Bin Ismail. "Monitoring of PV Performance Using LabVIEW." Indonesian Journal of Electrical Engineering and Computer Science 12, no. 2 (November 1, 2018): 461. http://dx.doi.org/10.11591/ijeecs.v12.i2.pp461-467.
Full textAbstract:
This project aims to design a simulator for PV monitoring using LabVIEW. This project will be divided into two parts ; software where LabVIEW and Arduino IDE been contracted and hardware parts. First part involves the software development. In this project, LabVIEW program is used as the main program to monitor the output of solar panel; voltage, current, power and temperature in real time. Next, the Arduino IDE program is used to interact the sensors with the Arduino board. The Arduino Uno microcontroller board is used as data acquisition medium to collect data from the solar panel. <span lang="EN-MY">Second, the hardware part which is PV panel setup and measurement circuit that consist of sensors and Arduino board so that the sensors data will transfer and display to the PC connected. In this simulator, the sensors are connected to the Analog I/O of Arduino Uno microcontroller which read the analogue input of sensors. The Arduino then is connected to the PC program LabVIEW to display the I-V graph and P-V graph. To make the data more significant, the data will be collected at the location 1.8635° N, 103.1089 ° E which is in Parit Raja, Batu Pahat, Johor. The data was collected with 3 different day and time; 12PM, 1PM and 2PM on 28/11/2017, 29/11/2017 and 30/11/2017.</span>