Combinatorics and Graph Theory

1709 Submissions

[4] viXra:1709.0242 [pdf] replaced on 2017-09-17 03:01:55

Exact Map Inference in General Higher-Order Graphical Models Using Linear Programming

Authors: Ikhlef Bechar
Comments: 50 Pages.

This paper is concerned with the problem of exact MAP inference in general higher-order graphical models by means of a traditional linear programming relaxation approach. In fact, the proof that we have developed in this paper is a rather simple algebraic proof being made straightforward, above all, by the introduction of two novel algebraic tools. Indeed, on the one hand, we introduce the notion of delta-distribution which merely stands for the difference of two arbitrary probability distributions, and which mainly serves to alleviate the sign constraint inherent to a traditional probability distribution. On the other hand, we develop an approximation framework of general discrete functions by means of an orthogonal projection expressing in terms of linear combinations of function margins with respect to a given collection of point subsets, though, we rather exploit the latter approach for the purpose of modeling locally consistent sets of discrete functions from a global perspective. After that, as a first step, we develop from scratch the expectation optimization framework which is nothing else than a reformulation, on stochastic grounds, of the convex-hull approach, as a second step, we develop the traditional LP relaxation of such an expectation optimization approach, and we show that it enables to solve the MAP inference problem in graphical models under rather general assumptions. Last but not least, we describe an algorithm which allows to compute an exact MAP solution from a perhaps fractional optimal (probability) solution of the proposed LP relaxation.
Category: Combinatorics and Graph Theory

[3] viXra:1709.0064 [pdf] submitted on 2017-09-06 05:06:03

Generalized Interval Valued Neutrosophic Graphs of First Type

Authors: Said Broumi, Assia Bakali, Mohamed Talea, Ali Hassan, Florentin Smarandache
Comments: 7 Pages. 2017 IEEE International Conference on INnovations in Intelligent SysTems and Applications (INISTA), Gdynia Maritime University, Gdynia, Poland, 3-5 July 2017.

In this paper, motivated by the notion of generalized single valued neutrosophic graphs of first type, we defined a new neutrosophic graphs named generalized interval valued neutrosophic graphs of first type (GIVNG1) and presented a matrix representation for it and studied few properties of this new concept. The concept of GIVNG1 is an extension of generalized fuzzy graphs (GFG1) and generalized single valued neutrosophic of first type (GSVNG1).
Category: Combinatorics and Graph Theory

[2] viXra:1709.0063 [pdf] submitted on 2017-09-06 05:08:06

Computation of Shortest Path Problem in a Network with SV-Triangular Neutrosophic Numbers

Authors: Said Broumi, Assia Bakali, Mohamed Talea, Florentin Smarandache
Comments: 6 Pages. 2017 IEEE International Conference on INnovations in Intelligent SysTems and Applications (INISTA), Gdynia Maritime University, Gdynia, Poland, 3-5 July 2017.

In this article, we present an algorithm method for finding the shortest path length between a paired nodes on a network where the edge weights are characterized by single valued triangular neutrosophic numbers. The proposed algorithm gives the shortest path length from source node to destination node based on a ranking method. Finally a numerical example is presented to illustrate the efficiency of the proposed approach
Category: Combinatorics and Graph Theory

[1] viXra:1709.0062 [pdf] submitted on 2017-09-06 05:14:18

Complex Neutrosophic Graphs of Type 1

Authors: Said Broumi, Assia Bakali, Mohamed Talea, Florentin Smarandache
Comments: 6 Pages. 2017 IEEE International Conference on INnovations in Intelligent SysTems and Applications (INISTA), Gdynia Maritime University, Gdynia, Poland, 3-5 July 2017

In this paper, we introduced a new neutrosophic graphs called complex neutrosophic graphs of type1 (CNG1) and presented a matrix representation for it and studied some properties of this new concept. The concept of CNG1 is an extension of generalized fuzzy graphs of type 1 (GFG1) and generalized single valued neutrosophic graphs of type 1 (GSVNG1).
Category: Combinatorics and Graph Theory