Computational complexity of problems of combinatorics and graph theory

M. M. Sysło. "Computational complexity of problems of combinatorics and graph theory." Mathematica Applicanda 8.16 (1980): null. <http://eudml.org/doc/293404>.

@article{M1980,
abstract = {From the introduction: "The present article does not pretend to be a complete survey of all or even of the most important algorithms in combinatorics and graph theory. The algorithms presented illustrate only general considerations involving the computational complexity of problems of combinatorics. It is assumed that the reader is acquainted with the fundamental algorithms of combinatorics and graph theory. The first part of the paper is an outline of basic computation models used in the analysis of combinatorial algorithms. In subsequent parts, problems for which optimal or `good' algorithms exist are discussed. Here problems connected with the class P are presented, i.e. the class of problems that can be solved by algorithms with polynomial complexity. A formal definition is given of the class P and the class NP, to which, with minor exceptions, all difficult problems-the knapsack problem, the scheduling problem, the problem of Hamiltonian circuits in graphs and networks, etc.-belong. The question whether P=NP is a fundamental problem in the analysis of the computational complexity of combinatorial algorithms. Contents: (1) Introduction; (2) Computational complexity of algorithms; (3) Computation models; (4) Ways of representing graphs, and the efficiency of algorithms; (5) Lower bounds of computational complexity; (6) Examples of optimal and `good' algorithms; (7) Problems with polynomial complexity; (8) Problems for which the existence of algorithms with polynomial complexity is not possible; (9) NP-complete problems; (10) Conclusion; Bibliography.},
author = {M. M. Sysło},
journal = {Mathematica Applicanda},
keywords = {Computational complexity and efficiency of algorithms; Exact categories, abelian categories; Network models, deterministic; Integer programming},
language = {eng},
number = {16},
pages = {null},
title = {Computational complexity of problems of combinatorics and graph theory},
url = {http://eudml.org/doc/293404},
volume = {8},
year = {1980},
}

TY - JOUR
AU - M. M. Sysło
TI - Computational complexity of problems of combinatorics and graph theory
JO - Mathematica Applicanda
PY - 1980
VL - 8
IS - 16
SP - null
AB - From the introduction: "The present article does not pretend to be a complete survey of all or even of the most important algorithms in combinatorics and graph theory. The algorithms presented illustrate only general considerations involving the computational complexity of problems of combinatorics. It is assumed that the reader is acquainted with the fundamental algorithms of combinatorics and graph theory. The first part of the paper is an outline of basic computation models used in the analysis of combinatorial algorithms. In subsequent parts, problems for which optimal or `good' algorithms exist are discussed. Here problems connected with the class P are presented, i.e. the class of problems that can be solved by algorithms with polynomial complexity. A formal definition is given of the class P and the class NP, to which, with minor exceptions, all difficult problems-the knapsack problem, the scheduling problem, the problem of Hamiltonian circuits in graphs and networks, etc.-belong. The question whether P=NP is a fundamental problem in the analysis of the computational complexity of combinatorial algorithms. Contents: (1) Introduction; (2) Computational complexity of algorithms; (3) Computation models; (4) Ways of representing graphs, and the efficiency of algorithms; (5) Lower bounds of computational complexity; (6) Examples of optimal and `good' algorithms; (7) Problems with polynomial complexity; (8) Problems for which the existence of algorithms with polynomial complexity is not possible; (9) NP-complete problems; (10) Conclusion; Bibliography.
LA - eng
KW - Computational complexity and efficiency of algorithms; Exact categories, abelian categories; Network models, deterministic; Integer programming
UR - http://eudml.org/doc/293404
ER -