Combinatorics and Graph Theory

1806 Submissions

[6] viXra:1806.0336 [pdf] submitted on 2018-06-22 07:08:11

Independence of Clique Problems

Authors: Thinh Nguyen
Comments: 27 Pages.

A polynomial algorithm is “faster” than an exponential algorithm. As n grows an (exponential) always grows faster than nk (polynomial), i.e. for any values of a and k, after n> certain integer n0, it is true that an > nk. Even 2^n grows faster than n1000 at some large value of n. The former functions are exponential and the later functions are polynomial. It seems that for some problems we just may not have any polynomial algorithm at all (as in the information theoretic bound)! The theory of NPcompleteness is about this issue, and in general the computational complexity theory addresses it.
Category: Combinatorics and Graph Theory

[5] viXra:1806.0238 [pdf] submitted on 2018-06-18 00:11:02

Linear Programming Solves Biclique Problems, Flaws in Literature Proof

Authors: Thinh D. Nguyen
Comments: 2 Pages.

The study of perebor dates back to the Soviet-era mathematics, especially in the 1980s [1]. Post-Soviet mathematicians have been working on many problems in combinatorial optimization. One of them is Maximum Edge Biclique Problem (MBP). In [2], the author proves that MBP is NP-complete. In this note, we give a polynomial time algorithm for MBP by using linear programming (LP). Thus, some flaw needs to be found in Peeter's work. We leave this to the community.
Category: Combinatorics and Graph Theory

[4] viXra:1806.0179 [pdf] submitted on 2018-06-14 03:30:42

Exact Weight Perfect Matching of Bipartite Graph Problem Simplified

Authors: Thinh D. Nguyen
Comments: 2 Pages.

The study of perebor dates back to the Soviet-era mathematics, especially in the 1980s [1]. Post-Soviet mathematicians has been working on many problems in combinatorial optimization. One of them is Exact Weight Perfect Matching of Bipartite Graph (EWPM).This particular problem has been thoroughly considered by [2], [3], [4]. In this note, we give a simpler proof about the solvability of EWPM.
Category: Combinatorics and Graph Theory

[3] viXra:1806.0065 [pdf] submitted on 2018-06-05 08:32:38

Proof of the Goldbach Conjecture

Authors: Zhuwenhao
Comments: 3 Pages.

This proves that any even number larger than 2 can be written as the sum of two prime Numbers, also known as the "goldbach conjecture" or "goldbach conjecture about the even" is in the test for any greater than or equal to 6 even conform to guess the number of prime Numbers, accidentally discovered the prime Numbers of "additionality" and further expansion of verification.This article does not focus on the functional expressions of prime Numbers themselves, but takes a different approach to prove that all even Numbers can be composed of two prime Numbers
Category: Combinatorics and Graph Theory

[2] viXra:1806.0049 [pdf] submitted on 2018-06-06 02:48:22

CSP Solver and Capacitated Vehile Routing Problem

Authors: Thinh D. Nguyen
Comments: 10 Pages.

In this paper, we present several models for Capacitated Vehicle Routing Problem (CVRP) using Choco solver. A concise introduction to the constraint programming methods is included. Then, we construct two models for CVRP. Experimental results for each model are given in details.
Category: Combinatorics and Graph Theory

[1] viXra:1806.0045 [pdf] replaced on 2018-06-08 08:27:08

Graph Isomorphism and Circuit Isomorphism

Authors: Thinh D. Nguyen
Comments: 4 Pages.

In this note, we show that graph isomorphism and some of its variant are both reducible to circuit isomorphism problem, in polynomial time.
Category: Combinatorics and Graph Theory