Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Computational Complexity

Sortuj według:

Ogranicz wyniki do:

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

Problems remaining NP-complete for sparse or dense graphs

100%

Schiermeyer I.

Discussiones Mathematicae Graph Theory

1995

tom 15

nr 1

33-41

For each fixed pair α,c > 0 let INDEPENDENT SET ($m ≤ cn^α$) and INDEPENDENT SET ($m ≥ (ⁿ₂) - cn^α$) be the problem INDEPENDENT SET restricted to graphs on n vertices with $m ≤ cn^α$ or $m ≥ (ⁿ₂) - cn^α$ edges, respectively. Analogously, HAMILTONIAN CIRCUIT ($m ≤ n + cn^α$) and HAMILTONIAN PATH ($m ≤ n + cn^α$) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with $m ≤ n + cn^α$ edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≥ (1 - ϵ)(ⁿ₂) edges. We prove that these six restricted problems remain NP-complete. Finally, we consider sufficient conditions for a graph to have a Hamiltonian circuit. These conditions are based on degree sums and neighborhood unions of independent vertices, respectively. Lowering the required bounds the problem HAMILTONIAN CIRCUIT jumps from 'easy' to 'NP-complete'.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Schiermeyer I.

1 1995

Wyniki wyszukiwania

Problems remaining NP-complete for sparse or dense graphs