The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with...The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.展开更多
A bipolar single-valued neutrosophic set can deal with the hesitation relevant to the information of any decision making problem in real life scenarios,where bipolar fuzzy sets may fail to handle those hesitation prob...A bipolar single-valued neutrosophic set can deal with the hesitation relevant to the information of any decision making problem in real life scenarios,where bipolar fuzzy sets may fail to handle those hesitation problems.In this study,we first develop a new method for solving linear programming problems based on bipolar singlevalued neutrosophic sets.Further,we apply the score function to transform bipolar single-valued neutrosophic problems into crisp linear programming problems.Moreover,we apply the proposed technique to solve fully bipolar single-valued neutrosophic linear programming problems with non-negative triangular bipolar single-valued neutrosophic numbers(TBSvNNs)and non-negative trapezoidal bipolar single-valued neutrosophic numbers(TrBSvNNs).展开更多
文摘The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
文摘A bipolar single-valued neutrosophic set can deal with the hesitation relevant to the information of any decision making problem in real life scenarios,where bipolar fuzzy sets may fail to handle those hesitation problems.In this study,we first develop a new method for solving linear programming problems based on bipolar singlevalued neutrosophic sets.Further,we apply the score function to transform bipolar single-valued neutrosophic problems into crisp linear programming problems.Moreover,we apply the proposed technique to solve fully bipolar single-valued neutrosophic linear programming problems with non-negative triangular bipolar single-valued neutrosophic numbers(TBSvNNs)and non-negative trapezoidal bipolar single-valued neutrosophic numbers(TrBSvNNs).
