Problems of the class NP : Research and simulating

Anatoly Plotnikov

ISBN 10: 3844393463 / ISBN 13: 9783844393460

Published by LAP LAMBERT Academic Publishing, 2011

About this Item

nach der Bestellung gedruckt Neuware - Printed after ordering - Problems of the class NP it's almost all problems solved on the computer. Therefore, this is extremely important and actually to research the properties of such problems and to construct their mathematical models, which allows in a number of cases to improve the solution algorithms or propose new ones. In studying the problems of the class NP we focused on the NP-complete problems, the researching their properties and constructing models. We construct a mathematical model of constructive combinatorial problems, clarify the concept of a class of problems solved by a non-deterministic Turing machine and define the concept of the problem without foresight, investigate the set-theoretic properties of extreme combinatorial problems. We offer the polynomial-time algorithm for the maxumum independent set problem based on a hypotheses. Also, we find a criterion for Hamiltonicity of a graph and consider some covering problems. This book should be especially useful to professionals in computer sience.

Seller Inventory # 9783844393460

Bibliographic Details

• Title: Problems of the class NP : Research and simulating
• Publisher: LAP LAMBERT Academic Publishing
• Publication Date: 2011
• Language: English
• ISBN 10: 3844393463
• ISBN 13: 9783844393460
• Binding: Taschenbuch
• Condition: Neu
• Dimensions: 220W x 150H x 10D millimeters 220 millimeters width by 150 millimeters height by 10 millimeters depth
• Weight: 244 grams

About this title

Synopsis

Problems of the class NP — it's almost all problems solved on the computer. Therefore, this is extremely important and actually to research the properties of such problems and to construct their mathematical models, which allows in a number of cases to improve the solution algorithms or propose new ones. In studying the problems of the class NP we focused on the NP-complete problems, the researching their properties and constructing models. We construct a mathematical model of constructive combinatorial problems, clarify the concept of a class of problems solved by a non-deterministic Turing machine and define the concept of the problem without foresight, investigate the set-theoretic properties of extreme combinatorial problems. We offer the polynomial-time algorithm for the maxumum independent set problem based on a hypotheses. Also, we find a criterion for Hamiltonicity of a graph and consider some covering problems. This book should be especially useful to professionals in computer sience.

About the Author

Anatoly Plotnikov is a professor of State University — the Dalh East-Ukrainian National University, Luhansk. He is also an associate member of AMS (USA) and a reviewer of the journal "Mathematical Reviews". His scientific interests include algorithms, combinatorial optimization, complexity theory.