Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Computational complexity of problems of combinatorics and graph theory

100%

Sysło M. M.

Mathematica Applicanda

|

1980

|

tom 8

|

nr 16

PL

.

EN

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.

2

Applied graph theory. Application of graph theory to numerical methods

100%

Sysło M. M.

Mathematica Applicanda

|

1975

|

tom 3

|

nr 5

EN

The author surveys the problems given in the title and their several generalizations. He considers both theoretical and algorithmic approaches. Some of his previous results are also included. He concludes the first part with an extensive bibliography of the subject. (MR0480181)

3

Algorithms 20-22. Fundamental set of cycles of a graph

75%

Sysło M. M.

Applicationes Mathematicae

|

1972-1973

|

tom 13

|

nr 3

399-409

4

Remarks on addition processes of positive floating-point numbers

75%

Sysło M. M.

Applicationes Mathematicae

|

1974-1975

|

tom 14

|

nr 3

415-417

5

New solvable cases of m-machine and n-element sequencing problems

64%

Grabowski J., Sysło M. M.

Applicationes Mathematicae

|

1974-1975

|

tom 14

|

nr 4

599-606

6

Algorithms 62-64. Graph-theoretic algorithms for sparse matrix transformations

64%

Dzikiewicz J., Sysło M. M.

Applicationes Mathematicae

|

1977-1980

|

tom 16

|

nr 2

353-378

7

Generalizations of the standard travelling salesman problem

63%

Sysło M. M.

Applicationes Mathematicae

|

1977-1980

|

tom 16

|

nr 4

621-629

8

A bisection method for the traveling salesman problem

63%

Sysło M. M.

Applicationes Mathematicae

|

1977-1980

|

tom 16

|

nr 1

59-62

9

Algorithm 36. Transitive closure of a graph

63%

Sysło M. M.

Applicationes Mathematicae

|

1974-1975

|

tom 14

|

nr 3

477-480

10

Computational experiments with some approximation algorithms for the travelling salesman problem

51%

Adrabiński A., Sysło M. M.

Applicationes Mathematicae

|

1983-1985

|

tom 18

|

nr 1

91-95

11

The calculation of α-sets of representatives

50%

Sysło M. M.

Applicationes Mathematicae

|

1972-1973

|

tom 13

|

nr 3

347-350

12

On some machine sequencing problems (II)

50%

Sysło M. M.

Applicationes Mathematicae

|

1974-1975

|

tom 14

|

nr 1

93-97

13

On a machine sequencing problem (I)

45%

Grabowski J., Sysło M. M.

Applicationes Mathematicae

|

1972-1973

|

tom 13

|

nr 3

339-345

14

A solvable case of the set-partitioning problem

38%

Sysło M. M.

Applicationes Mathematicae

|

1987

|

tom 19

|

nr 2

265-277

15

PROBLEMS

33%

Chrobak M., Habib M., John P., Sachs H., Zernitz H., Reay J. R., Sierksma G., Sysło M. M., Traczyk T., Wessel W.

Applicationes Mathematicae

|

1987

|

tom 19

|

nr 3-4

635-641

EN

1. Walls of rectangles (M. Chrobak) 2. Plane embeddings (M. Chrobak) 3. Cubic Hamiltonian graphs (M. Chrobak) 4. Jump number problem - 1 (M. Habib) 5. Domino covers in square chessboards (P. John, H. Sachs and H. Zernitz) 6. Interiors of uniform size in Steinitz's Theorem (J. R. Reay) 7. Area of lattice polygons - the $ 10 problem (J. R. Reay) 8. Regular graphs (G. Sierksma) 9. Jump number problem - 2 (M. M. Sysło) 10. Hamiltonian cycles in G² (T. Traczyk) 11. Thickness of graphs (W. Wessel)

16

Hamiltonian cycles in skirted trees

32%

Skowrońska M., Sysło M. M.

Applicationes Mathematicae

|

1987

|

tom 19

|

nr 3-4

599-610

Ograniczanie wyników

Computational complexity of problems of combinatorics and graph theory

Applied graph theory. Application of graph theory to numerical methods

Algorithms 20-22. Fundamental set of cycles of a graph

Remarks on addition processes of positive floating-point numbers

New solvable cases of m-machine and n-element sequencing problems

Algorithms 62-64. Graph-theoretic algorithms for sparse matrix transformations

Generalizations of the standard travelling salesman problem

A bisection method for the traveling salesman problem

Algorithm 36. Transitive closure of a graph

Computational experiments with some approximation algorithms for the travelling salesman problem

The calculation of α-sets of representatives

On some machine sequencing problems (II)

On a machine sequencing problem (I)

A solvable case of the set-partitioning problem

PROBLEMS

Hamiltonian cycles in skirted trees