All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 18 Next

Displaying 341 – 360 of 532

Showing per page

Persistency in the Traveling Salesman Problem on Halin graphs

Vladimír Lacko (2000)

Discussiones Mathematicae Graph Theory

For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition E A l l , E S o m e , E N o n e of the edge set E, where: E A l l = e ∈ E, e belongs to all optimum solutions, E N o n e = e ∈ E, e does not belong to any optimum solution and E S o m e = e ∈ E, e belongs to some but not to all optimum solutions.

Prescribed ultrametrics

J. Higgins, D. Campbell (1993)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Problems remaining NP-complete for sparse or dense graphs

Ingo Schiermeyer (1995)

Discussiones Mathematicae Graph Theory

For each fixed pair α,c > 0 let INDEPENDENT SET ( m ≤ c n α ) and INDEPENDENT SET ( m ≥ ( ⁿ ₂ ) - c n α ) be the problem INDEPENDENT SET restricted to graphs on n vertices with m ≤ c n α or m ≥ ( ⁿ ₂ ) - c n α edges, respectively. Analogously, HAMILTONIAN CIRCUIT ( m ≤ n + c n α ) and HAMILTONIAN PATH ( m ≤ n + c n α ) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≤ n + c n α edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted...

Currently displaying 341 – 360 of 532