Search

Graph ΓG = G(V, E) of some group G is called coprime, if V = G is finite and E = {gcd (|a|, |b|) = 1, a ≠ b}. Let G be group of units modulo n or U (n), the group of all positive integers less than n and relatively prime with n with respect to the modulo n multiplication. This article studies the properties of the coprime graph of group G = U (n), such as their planarity, radius, diameter, and degree. Therefore, we analyzed the properties of several examples of coprime graphs over some U(n) groups, then made conjectures, and proved it. In addition, it is also found that the coprime graph ΓU(n) is a complete bipartite graph and planar if and only if the U (n) group has order 2m for some positive integer m. [ABSTRACT FROM AUTHOR]

Let Km,m be the complete bipartite graph with m vertices in each partite set and Km,m⊕I indicates Km,m with a 1-factor added. In this Paper, We investigated the necessary and sufficient conditions for the existence of {λP5, µC4}−decomposition of Km,m ⊕ I when m ≡ 3 (mod 4) and λ ≠ 1. [ABSTRACT FROM AUTHOR]

The dominant metric dimension is the result of the development of graph theory, especially in the study of metric dimensions. The purpose of this research is to determine the dominant metric dimension on the vertex amalgamation v0l and v02, which are terminal vertices of graphs Gl and G2, respectively. The terminal vertex is a certain vertex that is set to each element of the graph collection that is carried out by the vertex amalgamation product. The vertex amalgamation product in this research is carried out on several special graphs including a complete bipartite graphs, a cycle graphs, a complete graphs, and a star graphs. From this research, it is found that Ddim(Amal{Gl; G2, v0l; v02 }) is the sum of the dominant metric dimensions of graphs Gl and G2 minus one or minus two where Gl and G2 are a complete bipartite graphs, a cycle graphs, a complete graphs and a star graphs. The results of this research indicate that the value of the dominant metric dimension of the vertex amalgamation product graph is influenced by the dominant basis, the order of graphs Gl and G2, and the terminal points of graphs Gl and G2. [ABSTRACT FROM AUTHOR]

The dominant metric dimension is the result of the development of the concept of metric dimension and dominant number in graph theory. This study aims to determine the dominant metric dimension of the edge corona product of a connected graph G and special graph H. The special graphs in here such as path graph, cycle graph, complete graph, and complete bipartite graph. As a result, the dominant metric dimension of the edge corona product graph depends on the size of graph G and the order of its special graph. [ABSTRACT FROM AUTHOR]

The concept of matching and coloring are the main problems in Combinatorics. Coloring of graphs and hypergraphs are well studied problems. In many cases, bipartite graphs provide simple solutions to graph problems than non bipartite graphs. In this paper we study about colorings in special types of hypergraphs. [ABSTRACT FROM AUTHOR]

A graph G(V, E) with p vertices and q edges is said to have a vertex odd root square mean graceful labeling if there exists a bijection M from V (G) to {1, 3, ...,2q+1} so that the induced mapping M* from E(G) to {3, 4, ..., 2q+1} given by: M * (e = cd)= ⌈ M(c) 2 + M(d) 2 2 ⌉ if |M(c)-M(d)| is even cd∈E(G) is an injective. Through this research work, we examine vertex odd root square mean graceful labeling on complete bipartite graph and some product graph. [ABSTRACT FROM AUTHOR]

This research analysis the internet pricing scheme model to maximize profits for ISPs (Internet Service Providers) by considering the utility function of Independent Goods. This study analyzes the types of flat-fee, usage-based, and two-part tariff pricing schemes for homogeneous consumers and heterogeneous consumers (high-end and low-end) and heterogeneous consumers (high-demand and low-demand). The pricing scheme model is then solved differentially by being applied to the local server data, SISFO traffic data. The results obtained are that ISPs will get maximum profit by implementing flat-fee, usage-based, and two-part tariff pricing schemes for homogeneous consumers. For high-end and low-end heterogeneous consumer types and high-demand and low-demand heterogeneous consumer types, the ISP will get maximum profit on the application of flat-fee, usage-based, and two-part tariff pricing schemes. However, ISPs will get the highest profit on homogeneous consumer types compared to the application of high-end and low-end heterogeneous consumer types and high-demand and low-demand heterogeneous consumers. [ABSTRACT FROM AUTHOR]

Here we introduced the Modified Laplacian Schultz matrix and, as a result, the Modified Laplacian Schultz energy. We offered lower and upper bounds for the Modified Laplacian Schultz energy. For standard graphs such as complete bipartite graphs, star graphs, friendship graphs, crown graphs, complete graphs, and cocktail graphs, Modified Laplacian Schultz energies are estimated. [ABSTRACT FROM AUTHOR]

In radio communication or wireless networks, transmitters are labeled with radio frequencies to avoid any interference in the signal communication. If the transmitters are close apart they receive close frequencies which results in interference between them. Mathematical modeling of these graphs is done by labeling the vertices of graphs. In radio labeling these vertices represent transmitters and closeness of frequencies is given by edges of graphs. In that article, radio mean labelling is done for different type of graphs for example lotus inside a circle with the introduction of radio mean number of graphs. In a graph, primary quantities vertex and edge set are represented by V(G) and E(G) respectively. Radio mean labelling is defined as a one to one mapping of f from V(G) to N that follows the condition.In the mapping from f to vertex set V(G), the maximum integer is defined as the radio span of f. The lowest radio span in all the functional mapping from f to V(G) is defined as radio mean number rmn(G) Here in, we report on rmn for different graphs like subdivision book graph, path, and total graph of path and subdivision of complete bipartite graph. [ABSTRACT FROM AUTHOR]

This work presents new contribution of graph theory for symmetric cryptographic applications. A tensor product bipartite graph (TPBG) is used to propose new symmetric encryption schemes. On proposed encryption schemes, the ciphertexts of the plaintexts are sent to receiver entity as the TPBGs. Based on two graphs G1 and G2, the TPBG is created depending on the random choices of the plaintext bits. These bits are used as vertices of graphs G1 and G2. The purpose for using the TPBG is to increase the security level of the symmetric encryption schemes in compare with other encryption schemes. Two study cases of the proposed symmetric TPB graphic (STPBG) encryption schemes are presented as new experimental results. The security issues of the proposed STPBG encryption schemes are determined. The STPBG encryption schemes consider as new insights for more secure communications. [ABSTRACT FROM AUTHOR]

In this paper, the relationship between the algebra and graph theory are been studied especially the zero divisor graph in the ring ZN and constitute graph of these element Γ(Zn). The graph obtained by the above relation are isomorphic to some certain graphs as a complete and complete bipartite graph. The number of some vertices of Γ(Zn) are been introduced. Also, the domination of the zero divisor graph to some certain graphs are been determined. [ABSTRACT FROM AUTHOR]

Throughout this research, the corona operation of a cycle graph and one of the certain graphs such as wheel, path, cycle, complete, star, complete bipartite, and null graph for even sum domination. Also, for each case there are some figures are been introduced to illustrated these cases. [ABSTRACT FROM AUTHOR]

Spatial models have attracted considerable interest in the recent economics both on an empirical and theoretical level. One of the most widely used spatial models is the single equation model. Spatial simultaneous equation model as an extension of the widely used spatial single equation model and can uses more than one equations. Simultaneous equation models using panel data, especially for fixed effect with two way error component where there are spatial autoregressive still few of their development and requaire to be developed. This paper proposed Generalized Spatial two stage least square (GS2SLS) two way error component model to describes the simultaneous relationship between four inclusive growth indicators and spatial linkages between regions in 34 provinces in Indonesia (2015-2019) The results prove that there are simultaneous relationships between the four indicators and spatial linkages between regions in Indonesia. [ABSTRACT FROM AUTHOR]

In literature, product of graphs has been used to generate mathematical models of complex networks which resembles the properties of real networks. These properties can be imbibed in the concept of corona product of two graphs. In this paper we define the star coloring on corona product of two fuzzy graphs and determine the star chromatic number of corona product of two fuzzy graphs such as fuzzy path graph with fuzzy complete graph on the same order n, fuzzy star graph on order n+1 with fuzzy complete graph, fuzzy path graph with fuzzy star graph on order n+1 and fuzzy path graph with fuzzy complete bipartite graph. We also find the relation between the star chromatic number of a fuzzy graph and star chromatic number of underlying crisp graph. [ABSTRACT FROM AUTHOR]

Let G=(V, E) be a non-isolated graph. A Co-Secure dominating set D is said to be a Co-Secure Set Dominating Set if for each subset T ⊆ V - D there exist a non-empty set S of D such that the induced subgraph 〈T ∪ S〉 is connected and it's abbreviated as CSSDS of G. The Co-secure set domination number is denoted as γ c s s (G) and is defined as the cardinality of smallest co-secure set dominating set.[3] Throughout this paper, we investigate the γ c s s (G) of central graph of G. We determine the γ c s s (G) of Central graph of path graph, complete graph, cycle graph, star, complete bipartite and wheel graph explicitly and we obtain the sharp bounds for γ c s s (C (G)) . [ABSTRACT FROM AUTHOR]

A bipartie graph G(V0 ∪V1, E) is said to be Hamiltonian laceable, if there exists a u − v H-path such that u∈ V0 and v ∈ V1. A non bipartite graph G(V, E) is defined to be random hamiltonian laceable, if there is a u - v H-path ∀ u, v ∈ V and it is defined to be partial random hamiltonian laceable, if there is a u - v H-path ∀ u, v ∈ V thus d(u, v) = t, where t is either odd or even. Cayley graphs are special class of graphs that are suitable for designing interconnection networks. Hamiltonian laceability of families of Cayley graphs namely Knödel Graph and Cube connected complete graph are studied in this research article. [ABSTRACT FROM AUTHOR]

An acyclic coloring is a proper vertex coloring in which no cycle in the graph is bichromatic. The acyclic chromatic number a(G) of a graph G is the least number of colors in an acyclic coloring of G. In this paper, the concept of ideal acyclic chromatic sum IACS, of a graph G=(V, E), denoted by ΣIa(G) is introduced. Also, the ideal acyclic chromatic sum of basic graphs like paths, cycles, wheel graphs, star graphs, trees, complete graphs, complete bipartite graphs are studied and a bound for IACS of an arbitrary graph is obtained. [ABSTRACT FROM AUTHOR]

This research has been dealt with the modern Roman domination on complement of certain graphs such as path, cycle, complete bipartite, star, wheel, complete,and null,also we characterized the Corona operation of two certain graphs. [ABSTRACT FROM AUTHOR]

With the swift proliferation of handheld mobile devices, location based social networking (LBSNs) services have gained immense attention allowing users to discover their point of interest (POI). Application of collaborative filtering techniques in POI recommendation becomes challenging due to the sparsity of large user ­POI rating matrix. Further, in the context of LBSNs, the spatiotemporal information is pivotal to capture user’s real ­time preferences. In this work we propose a graph based POI recommendation approach, Context Aware POI with Social Trust (CAST ) which integrates the geographical influence of the POIs and the influence of the social connections with the user rankings derived from the weighted bipartite graph. Experiments have been conducted with six state­ of ­the ­art baselines using two real world LBSN data sets. Findings reveal that user ranking on bipartite graph is a significant contributor to the performance along with social, geographical and spatial influence. [ABSTRACT FROM AUTHOR]

Online algorithms for secretary matching in bipartite weighted graphs have been studied extensively in recent years. We generalize this study to secretary matching in general weighted graphs, for both vertex and edge arrival models. Under vertex arrival, vertices arrive online in a uniformly random order; upon the arrival of a vertex v, the weights of edges from v to all previously arriving vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. We provide a tight 5/12-competitive algorithm for this setting. Interestingly, it outperforms the best possible algorithm for secretary matching in bipartite graphs with 1-sided arrival, which cannot be better than 1/e-competitive. Under edge arrival, edges arrive online in a uniformly random order; upon the arrival of an edge e, its weight is revealed, and the algorithm decides whether to include it in the matching or not. For this setting we provide a 1/4-competitive algorithm, which improves upon the state of the art bound. [ABSTRACT FROM AUTHOR]

Thamarai Selvi and Vaidya Nathan [2] discussed maximum distance on graphs. We made an extension of that paper [2]. We discussed about complete graph Kn, star graph Sn, the complete bipartite graph Km,n. In this paper, we studied about the cycle graph Cn (n being any interger ≥ 3) and the multi star graph Bm,n, where m, n are integers, both greater than or equal to 2. [ABSTRACT FROM AUTHOR]

Matrix reordering techniques are essential to reveal patterns in tabular visualizations (such as heatmaps). Polar Sort is a state-of-the-art, pattern-focused reordering method that uses a multidimensional projection technique - Classical MDS - to reveal Band and Circumplex patterns in reorderable matrices. However, Polar Sort is not scalable due to Classical MDS' asymptotic time complexity (O(n?)). In this paper, we explore the use of a fast multidimensional projection technique - FastMap (O(n)) - as an alternative to Classical MDS inside Polar Sort. The new reordering algorithm - PSF - reorders rows and columns of a matrix according to bidimensional projections projected by FastMap (instead of Classical MDS), and uses a barycenter-based ordering identical to Polar Sort's approach. The results of an experiment with synthetic matrices point out that PSF maintained the output quality of its predecessor (according to minimal span loss function, Moore stress, and circular correlation) and had lower execution time than other compared methods. We present the results of these experiments and also some examples of real-world matrices that show patterns similar to Band and Circumplex when reordered by PSF. [ABSTRACT FROM AUTHOR]

With very few exceptions, recent research in fair division has mostly focused on deterministic allocations. Deviating from this trend, we study the fairness notion of interim envy-freeness (iEF) for lotteries over allocations, which serves as a sweet spot between the too stringent notion of ex-post envy-freeness and the very weak notion of ex-ante envy-freeness. iEF is a natural generalization of envy-freeness to random allocations in the sense that a deterministic envy-free allocation is iEF (when viewed as a degenerate lottery). It is also certainly meaningful as it allows for a richer solution space, which includes solutions that are provably better than envy-freeness according to several criteria. Our analysis relates iEF to other fairness notions as well, and reveals tradeoffs between iEF and efficiency. Even though several of our results apply to general fair division problems, we are particularly interested in instances with equal numbers of agents and items where allocations are perfect matchings of the items to the agents. Envy-freeness can be trivially decided and (when it can be achieved, it) implies full efficiency in this setting. Although computing iEF allocations in matching allocation instances is considerably more challenging, we show how to compute them in polynomial time, while also maximizing several efficiency objectives. Our algorithms use the ellipsoid method for linear programming and effcient solutions to a novel variant of the bipartite matching problem as a separation oracle. We also study the extension of interim envy-freeness notion when payments to or from the agents are allowed. We present a series of results on two optimization problems, including a generalization of the classical rent division problem to random allocations using interim envy-freeness as the solution concept. [ABSTRACT FROM AUTHOR]

ABSTRACT In this paper, we use Prufer’s construction and exponential generating function to find the formula of the number of labelled tree with r1, r2 end-vertices in complete bipartite graph Km,n denoted by L(m, n, r1, r2). For 2 m ≤ n,L(m,n,r1,r2)=(mr1)(nr2)Ar1Ar2 where Ar1=∑i=0m−1(−1)i(m−r1i)(m−r1−1)n−1 and Ar2=∑j=0n−1(−1)j(n−r2j)(n−r2−1)m−1. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a graph. A function f: V → {0, 1} of the graph G is called a Biconditional cordial labeling of G if an induced edge function f*: E → {0, 1} defined by f*(uv)= { 1 , if f(u)=f(v) 0 , if f(u) ≠ f(v) satisfies the following two conditions. i) | v f (0) − v f (1) | ≤ 1 ii) | e f * (0) − e f * (1) | ≤ 1 In this manuscript, we prove the existence of the Biconditional cordial labeling for complete bipartite graph, book graph with triangular pages, sunflower graph and web graph. [ABSTRACT FROM AUTHOR]

In this paper, we introduced the concept of minimum covering color Laplacian energy L E χ C (G) of a graph G and computed minimum covering chromatic Laplacian energies of star graph, complete graph, crown graph, bipartite graph and cocktail graphs. Upper and lower bounds for L E c C (G) are also established. [ABSTRACT FROM AUTHOR]

The concept of topology has great significance in the study of spatial objects and their associated problems encountered in Physics. In topology, a discrete space is an example of a topological space in which the points form a discontinuous sequence, meaning they are isolated from each other in a certain sense. In this paper, we introduce the concept of Discrete Metric Graphs which is derived from the concept of Discrete Metric Space in Topology. Let G(V,E) be an undirected graph, then the Discrete Metric Graph of G denoted by D(G) is the graph whose any two vertices u and v are connected if deg(u)≠deg(v) in G. The properties of the Discrete Metric Graphs of some standard graphs such as path, regular graph, cycle, complete graph, complete bipartite graph, star, wheel, etc... have been studied in this paper. [ABSTRACT FROM AUTHOR]

For a connected graph G(V,E), let S ⊆ V(G) be a minimum strong geodetic set of G then a non-extreme vertex v ∈ S is said to be S-extreme vertex if v is not geodominated by any pair of vertices of G. A strong geodetic set S of vertices in a connected graph G is an strong open geodetic set if for each vertex v ∈ G, either v is a S-extreme vertex of G and v ∈ S or v is an internal vertex of an x — y geodesic for some x,y ∈ S. A strong open geodetic set of minimum cardinality is a minimum strong open geodetic set and this cardinality is the strong open geodetic number of a graph G, denoted by sog(G). In this paper we have discussed about some results related to open geodetic sets. Also, mainly we have the complexity property of strong open geodetic set problem for general graphs, chordal graphs, chordal bipartite graphs. Further few general results and some bounds are given to the strong open geodetic number of some graphs. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a graph. A vertex v is k–geodominated by a pair x,y ⊆ V(G), if v lies on an x – y geodesic of G of length exactly k. A set S ⊆ V(G) is a strong (k, r)geodetic set if each vertex v ∈ G/S lies on at least r distinct fixed k–geodesics between the pair of vertices in S. The minimum cardinality of the strong (k, r) geodetic set is a strong (k, r) geodetic number and is denoted by sg(k,r)(G). In this paper we prove that the strong (k, r) geodetic set is NP–complete for general graphs, bipartite graphs, chordal graphs and chordal bipartite graphs. Also we derived some results on strong (2,2) geodetic number. [ABSTRACT FROM AUTHOR]

In this article we have defined a new matrix called Laplacian Schultz matrix and hence Laplacian Schultz energy. Upper and lower bounds for Laplacian Schultz energy are presented. At the end of this article Laplacian Schultz energies for some standard graphs like star graph, complete graph, crown graph, cocktail graph, complete bipartite graph and friendship graphs are computed. [ABSTRACT FROM AUTHOR]

Let G1, G2, G3,…, Gn be connected subgraph of G. If E(G) = E(G1)∪E(G2)∪ … ∪E(Gn) and E(Gi) ∩ E(Gj) = ø for any i ≠ j, then (G1, G2, G3,…, Gn) is a decomposition of G. The even star decomposition (S2, S4,…, S2t) of a complate bipartite graph Km,n, where Si is a star with i vertices of degree 1, has been studied by Merley and Goldy in 2016. In this paper we study an odd star decomposition (S1, S3, S5,…, S2t-1) of a complete bipartite graph Km,n when 1 ≤ m ≤ 5. [ABSTRACT FROM AUTHOR]

We characterize the class of group-strategyproof mechanisms for the single facility location game in any unconstrained strictly convex space. A mechanism is group-strategyproof, if no group of agents can misreport so that all its members are strictly better off. A strictly convex space is a normed vector space where ||x +y|| < 2 holds for any pair of different unit vectors x ≠ y, e.g., any Lp space with p ∈ (1, ∞). We show that any deterministic, unanimous, group-strategyproof mechanism must be dictatorial, and that any randomized, unanimous, translation-invariant, group-strategyproof mechanism must be 2-dictatorial. Here a randomized mechanism is 2-dictatorial if the lottery output of the mechanism must be distributed on the line segment between two dictators' inputs. A mechanism is translation-invariant if the output of the mechanism follows the same translation of the input. Our characterization directly implies that any (randomized) translation-invariant approximation algorithm satisfying the group-strategyproofness property has a lower bound of 2-approximation for maximum cost (whenever n ≥ 3), and n/2 - 1 for social cost. We also find an algorithm that 2-approximates the maximum cost and n/2-approximates the social cost, proving the bounds to be (almost) tight. [ABSTRACT FROM AUTHOR]

We consider a combinatorial variant of the classical ski rental problem -- which we call combinatorial ski rental -- where multiple resources are available to purchase and to rent, and are demanded online. Moreover, the costs of purchasing and renting are potentially combinatorial. The dual problem of combinatorial ski rental, which we call combinatorial online bipartite matching, generalizes the classical online bipartite matching problem into a form where constraints, induced by both offline and online vertices, can be combinatorial. We give a 2-competitive (resp. e/(e - 1)-competitive) deterministic (resp. randomized) algorithm for combinatorial ski rental, and an e/(e - 1)-competitive algorithm for combinatorial online bipartite matching. All these ratios are optimal given simple lower bounds inherited from the respective well-studied special cases. We also prove information-theoretic impossibility of constant-factor algorithms when any part of our assumptions is considerably relaxed. [ABSTRACT FROM AUTHOR]

We consider Bayesian online selection problem of a matching in bipartite graphs, i.e., online weighted matching problem with edge arrivals where online algorithm knows distributions of weights, that corresponds to the intersection of two matroids in Kleinberg andWeinberg [35] model. We consider a simple class of non adaptive vertex-additive policies that assign static prices to all vertices in the graph and accept each edge only if its weight exceeds the sum of the prices of the edge's endpoints. We show existence of a vertex-additive policy with the expected payoff of at least one third of the prophet's payoff and present gradient decent type algorithm that quickly converges to the desired vector of vertex prices. This improves the adaptive online policy of [35] for the intersection of two matroids in two ways: our policy is non adaptive and has better approximation guarantee of 3 instead of previous guarantees 5.82 of Kleinberg and Weinberg and 2 · e = 5.43 of Feldman et al. [23] against the prophet. We give a complementary lower bound of 2.25 for any online algorithm in the bipartite matching setting. [ABSTRACT FROM AUTHOR]

The objective of establishing the HIV-1 Human Interaction Database (HHPID) in the NCBI that is to encourage the scientists to produce more publications. The database collates two types of interactions from the published reports - protein interactions and replication interactions. One of the growing up data mining technique is bioinformatics is biclustering. The BicBin algorithm is one of the biclustering method to a binary matrix. We propose a systematic procedure to make biclusters to the HHPID using BicBin algorithm. First, we select the HIV-1 proteins, the human proteins, and the interaction keywords from HHPID to model the interaction as a bipartite graph. The Keywords are divided into three classes based on the direction of the interactions and then separated them into two binary matrices, i.e., positive and negative matrix. The binary matrices then become the input to the BicBin algorithm. The algorithm outputs many biclusters. The user sets the input parameter α and β to control the search area in each binary matrix. The parameter p1 is used to control the density of the biclusters. Then, the algorithm is iterated by parameter I. We set α = 0.5, β = 0.5, p1 = 1, and I = 600 in our procedure. [ABSTRACT FROM AUTHOR]

If we create intelligent automated systems, decision support systems, expert systems, and in general knowledge-based systems then the development of the inference mechanism is very important. This mechanism of inference makes it possible to carry out reasoning on the available knowledge and data, to develop recommendations and decisions, to make their justifications and explanations. In this paper, a model of inference in the form of a bipartite graph is considered. The elements of the graph correspond to clauses, literals of clauses, and complement pairs of literals. This gives the initial structure for the inference procedure. The logical inference is carried out step by step. At each step, we make local changes to the graph. The inference ends positively if the graph is transformed into one vertex of the first or second type. The conclusion ends negatively if the next step cannot do. Note that we didn’t model getting of the resolvent according to the resolution principle. However, the proposed structure is able to model both the resolution method and the inverse method. Moreover, it allows you to simulate these methods not only separately. It is possible to obtain a hybrid from the step-by-step application of the methods alternately. At the same time, the resolution method received from us a considerable generalization. Getting the resolvent was made possible not only from a pair of clauses, but also from any number of clauses, for example, one or three. The proposed new mechanism of inference in its expressiveness is equal to the resolution method. It got the software implementation and showed good results. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel, flat analytic timing-driven placer without explicit packing for Xilinx UltraScale FPGA devices. Our work uses novel methods to simultaneously optimize for timing, wirelength and congestion throughout the global and detailed placement stages. We evaluate the effectiveness of the flat placer on the ISPD 2016 benchmark suite for the xcvu095 UltraScale device, as well as on industrial benchmarks. Experimental results show that on average, FTPlace achieves an 8% increase in maximum clock rate, an 18% decrease in routed wirelength, and produces placements that require 80% less time to route when compared to Xilinx Vivado 2018.1. [ABSTRACT FROM AUTHOR]

Let H and G be two simple graphs. The topic of an H-magic decomposition of G arises from the combination of graph decomposition and graph labeling. A decomposition of a graph G into isomorphic copies of a graph H is H - magic if there is a bijection f:V(G) ∪ E(G) → {1,2,…, V(G) ∪ E(G)|}such that the sum of labels of edges and vertices of each copy of H in the decomposition is constant. A lexicographic product of two graphs G1 and G2, denoted by G1[G2], is a graph which arises from G1 by replacing each vertex of G1 by a copy of the G2 and each edge of G1 by all edges of the complete bipartite graph Kn,n where n is the order of G2. In this paper we show that for n ≥ 4 and m ≥ 2, the lexicographic product of the cycle graphs complement and complete graphs complement Cn[Km] has P2[Km]-magic decomposition if and only if m is even, or m is odd and n ≡ 1 (mod4), or m is odd and n ≡ 2 (mod4), or m is odd and n ≡ 2(mod4) . [ABSTRACT FROM AUTHOR]

A graph is a set of vertices and edges where each edge connects two vertices in the graph. There are several ways to represent a graph, e.g., it can be represented as a matrix: its adjacency matrix, anti-adjacency matrix, Laplacian matrix, or distance matrix. Two matrices which will be explored in this paper are the adjacency matrix and distance matrix. The adjacency matrix represents the presence or absence of an edge connecting two vertices, while the distance matrix represents the shortest path between two vertices. A graph with diameter two is a graph such that the longest distance between any two vertices is equal to two. Examples of two-diameter graphs include bipartite graphs, wheel graphs, and fan graphs. The relation between the distance and adjacency matrices is already known. The purpose of this paper is to find the relation between the square of the distance matrix and the square of the adjacency matrix of a two diameter graph and to find the characteristic polynomial of the distance matrix of a complete bipartite graph Kn,n(which is a special type of two-diameter graph). We prove that D² = 4(J-I)Ā + A2 where D is the distance matrix, J is the matrix all of whose entries are 1, I is the identity matrix, A is the adjacency matrix and Ā is the complement of A Moreover, we also find that the characteristic polynomial of the distance matrix of a complete p bipartite graph is P(λ) = (λ+2)2n-2(λ-(n-2))(λ-(3n-2)). [ABSTRACT FROM AUTHOR]

We consider the stochastic matching problem. An edge-weighted general (i.e., not necessarily bipartite) graph G(V, E) is given in the input, where each edge in E is realized independently with probability p ; the realization is initially unknown, however, we are able to query the edges to determine whether they are realized. The goal is to query only a small number of edges to find a realized matching that is sufficiently close to the maximum matching among all realized edges. The stochastic matching problem has received a considerable attention during the past decade after the initial paper of Chen et al. [ICALP'09] because of its numerous real-world applications in kidney-exchange, matchmaking services, online labor markets, and advertisements. Most relevant to our work are the recent papers of Blum et al. [EC'15], Assadi et al. [EC'16, EC'17] and Maehara and Yamaguchi~[SODA'18] that consider the same model of stochastic matching. Our main result is an adaptive algorithm that for any arbitrarily small ε > 0, finds a (1-ε)-approximation in expectation, by querying only O(1) edges per vertex. We further show that our approach leads to a (1/2-ε)-approximate non-adaptive algorithm that also uses $O(1)$ edges per vertex. Prior to our work, no nontrivial approximation was known for weighted graphs using a constant per-vertex budget. The state-of-the-art adaptive (resp. non-adaptive) algorithm of Maehara and Yamaguchi achieves a (1-ε)-approximation (resp. (1/2-ε)-approximation) by querying up to O(w łogn) edges per vertex where w denotes the maximum integer edge-weight. Our result is a substantial improvement over this bound and has an appealing message: No matter what the structure of the input graph is, one can get arbitrarily close to the optimum solution by querying only a constant number of edges per vertex. To obtain our results, we introduce novel properties of a generalization of augmenting paths to weighted matchings that may be of independent interest. [ABSTRACT FROM AUTHOR]

A labeling f : V (G) → Z+ such that |f(u) − f(v)|≥diam(G) + 1 − d(u, v) holds for every u, v ∈ V (G), is called a radio labeling of G. We define the radio degree of a labeling f : V (G) → {1, 2, … |V (G)|} as the number of pairs of vertices u, v ∈ V (G) satisfying the condition |f(u) - f(v)|≥diam(G) + 1 - d(u, v) and denote it by rdeg(f). The maximum value of rdeg(f) taken over all such labelings is defined as the radio degree of the graph denoted by rdeg(G). In this paper, we find the radio degree of some standard graphs like paths, cycles, complete graphs, complete bipartite graphs and also obtain a characterization of graphs of diameter two that achieve the maximum radio degree. [ABSTRACT FROM AUTHOR]

Qmodel Creator is a software for designing block (LEGO) style 3D models using intuitive drawing methods. The produced models are composed of cubes, which are conveniently encoded using voxel-based representation. To support content-based search and retrieval for models generated with Qmodel Creator, we proposed a feature descriptor defined as 3D local ternary descriptor (3DLTD) in this paper. To begin with, we partition the bounding box of each model into cubes and then divide cubes into voxels. Weights are assigned to each voxel according to its distance to the boundary. We randomly select 64 pairs of voxels in each cube and generate a ternary code based on the relationship between each pair of voxels. Weighted bipartite matching is employed to compute the similarity between two models. Experimental results indicate that 3DLTD is suitable for comparing and searching voxel-based 3D models. Compared with 3DBRIEF, our proposed framework is more robust and efficient thanks to the two-level partition. Ternary encoding also promotes feature representativeness and noise immunity while maintaining overall efficacy. [ABSTRACT FROM AUTHOR]

In this paper, the restricted detour polynomials and restricted detour indices for prescribed graphs called thorn rings, cog-cycles, thorn cog-cycles are obtained. [ABSTRACT FROM AUTHOR]

In this talk we propose a graphical representation of some classes of Leibniz algebras. With each of algebra from these classes we associate a graph. This assignment enables us to reformulate some structural properties of the Leibniz algebras in terms of some conditions for the graphs. The talk focuses on a so-called filiform Leibniz algebras. It is well-known that this class is split into three subclasses called first, second and third class denoted, in dimension n over a field K, by FLbn(K), SLbn(K) and TLbn(K), respectively. In this article, we concern more on the combinatorial structures associated with SLbn(K) in low-dimensions. [ABSTRACT FROM AUTHOR]

Let G be a graph with V(G) = {v1, ..., vn} and E(G) = {e1, ... em}. We only consider undirected graphs with no multiple edges in this paper. The adjacency matrix of G, denoted by A(G), is the n x n matrix A = [aij], where aij = 1 if e = vivj ∈ E(G) or otherwise aij = 0. The anti adjacency matrix of G, denoted by B(G), is the n x n matrix B = [bij], where bij = 0 if e = vivj ∈ E(G) or otherwise bij = 1. Properties of the determinant of the adjacency matrix of some simple graphs have been studied by many researchers. However, the determinant of the anti-adjacency matrix has not been explored yet. If G1 and G2 are disjoint graphs, then the joining of two graphs G1 and G2, denoted G1 ▽ G2 is defined by taking copies of G1 and G2 and adding edges so that each vertex in G1 is adjacent to every vertex in G2. In this paper, we show the properties of the determinant of joining two graphs, G1 and G2. Union of two graphs, denote G1 ∪ G2 is a graph formed by taking copies of G1 and G2. The objectives of this paper are to identify some properties of the determinant anti adjacency matrix of joining and union operation from two disjoint graphs. This paper also emphasizes on investigating the determinant of some special graph class formed by joining and unioning operation of two disjoint of several classes of graphs, such as Bipartite graphs, Cycles, Complete graphs, Stars, and Wheels. [ABSTRACT FROM AUTHOR]

We can observe self-organized networks all around us. These networks are, in general, scale invariant networks described by the Bianconi-Barabasi model. The self-organized networks (networks formed naturally when feedback acts on the system) show certain universality. These networks, in simplified models, have scale invariant distribution (Pareto distribution type I) and parameter α has value between 2 and 5. The textbooks are extremely important in the learning process and from this reason we studied physics textbook at the level of sentences and physics terms (bipartite network). The nodes represent physics terms, sentences, and pictures, tables, connected by links (by physics terms and transitional words and transitional phrases). We suppose that learning process are more robust and goes faster and easier if the physics textbook has a structure similar to structures of self-organized networks. [ABSTRACT FROM AUTHOR]

Extracting similar datapath bit slices which handle highly parallel bit operations can help a modern placer to obtain better solutions for datapathoriented designs. A current state-of-the-art datapath bit slicing method achieves the best extraction results using a network-flow-based algorithm. However, this work has two major drawbacks: (1) it extracts only a limited number of bit slices for datapaths with different I/O widths, which are commonly seen in real designs, and (2) it does not consider bit-slice similarity, which is an important feature for placement considering datapaths. To remedy these drawbacks, we present (1) a balanced bipartite edge-cover algorithm to fully slice a datapath with different I/O widths, and (2) a simulated annealing scheme to further improve bit-slice similarity, while maintaining fully-sliced structures. Compared with the state-of-the-art work, experimental results show that our slicing algorithm extracts more bit slices with similar structures, and helps a leading academic placer achieve averagely 5% smaller routed wirelength. The results also validate the high correlation between datapaths and structure regularity/similarity. [ABSTRACT FROM AUTHOR]

The main objective of this work is to study Markov bases and toric ideals for p(v-1)(p-v)/2v × v × p/v-contingency tables that has fixed two-dimensional marginal when p is a multiple of v and greater than or equal to 2v. Moreover, the connected bipartite graph is also constructed by using elements of Markov basis. This work is an extension on results, that has been found by Hadi and Salman in 2014. [ABSTRACT FROM AUTHOR]

We study the classic online bipartite matching problem with a twist: offline nodes are reusable any number of times. Every offline node i becomes available d steps after it was assigned to. Nothing better than a 0.5-approximation, obtained by the trivial deterministic greedy algorithm, was known for this problem. We give the first approximation factor beating 0.5, namely a 0.505 approximation, by suitably adapting and interpreting the powerful technique of Online Correlated Selection. [ABSTRACT FROM AUTHOR]

The diffusion of innovations is a central problem in the study of social networks. Although a considerable amount of attention has been paid to when innovations are adopted, few studies have considered the reverse process of when innovations are abandoned. We examine this process among employees in a large technology company using a unique dataset on the use of an enterprise collaboration system - an innovative software tool used to help employees collaborate with one another. The data consider a bipartite network of over 49,000 employees connected by over 26,000 communities, over a time period of around 4 years. Using timestamped data on posts to the software, we construct a real-time measure of when an employee begins using the software and ultimately abandons the software. We find that employees are more likely to stop using the software when the software has lesser value for them. Value is measured as the number of other users of the software. We consider value both locally - the number of other users that someone is connected to - and globally - the number of users in the company as whole. Our findings shed light on use in different areas of an organization can cascade into widespread adoption or abandonment, and on the diffusion of innovations process as a whole. [ABSTRACT FROM AUTHOR]