Discussions of NP-Complete Problems

A Resource for Computer Science Educators

Home
About the SIte
Bibliography
How to get the archive password

Tag Archives: No G&J reference

Protected: Maximum Leaf Spanning Tree, Connected Dominating Set

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Appendix- Network Design and tagged Difficulty 2, Difficulty 5, Dominating Set, Hamiltonian Path, ND2, No G&J reference, Not in Appendix, uncited reduction, Vertex Cover on October 13, 2015 by Sean T. McCulloch.

Protected: Degree Constrained Spanning Tree

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Appendix- Network Design and tagged Degree Constrained Spanning Tree, Difficulty 1, Hamiltonian Path, ND1, No G&J reference, uncited reduction on October 6, 2015 by Sean T. McCulloch.

Protected: Maximum Subgraph Matching

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Appendix-Graph Theory and tagged Clique, Difficulty 2, Difficulty 5, GT48, GT50, Largest Common Subgraph, Maximum Subgraph Matching, No G&J reference, Subgraph Isomorphism, uncited reduction on June 23, 2015 by Sean T. McCulloch.

Protected: Elimination Degree Sequence

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Appendix-Graph Theory and tagged Difficulty 6, Elimination Degree Sequence, No G&J reference, uncited reduction, X3C on June 16, 2015 by Sean T. McCulloch.

Protected: Hamiltonian Completion

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Appendix-Graph Theory and tagged Difficulty 1, Difficulty 2, GT33, Gt34, Hamiltonian Circuit, Hamiltonian Completion, Hamiltonian Path, No G&J reference, uncited reduction on March 10, 2015 by Sean T. McCulloch.

Protected: Partition into Forests

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Appendix-Graph Theory and tagged Difficulty 6, Graph 3-coloring, GT14, No G&J reference, Partition Into Forests, uncited reduction on October 22, 2014 by Sean T. McCulloch.

Protected: Dominating Set

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Chapter 3 Exercises and tagged Difficulty 4, Dominating Set, GT2, No G&J reference, reductions, uncited reduction, Vertex Cover on July 15, 2014 by Sean T. McCulloch.

Protected: Minimum Sum of Squares

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Appendix- Sets and Partitions, Chapter 3 Exercises and tagged Difficulty 3, MSS, No G&J reference, Part, reductions, SP19, uncited reduction on July 8, 2014 by Sean T. McCulloch.

Protected: Largest Common Subgraph

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Chapter 3 Exercises and tagged Clique, Difficulty 3, GT49, Largest Common Subgraph, No G&J reference, reductions, uncited reduction on July 1, 2014 by Sean T. McCulloch.

Protected: Longest Path

Enter your password to view comments.

This content is password-protected. To view it, please enter the password below.

Password:

This entry was posted in Chapter 3 Exercises and tagged Difficulty 1, Hamiltonian Path, Longest Path, ND29, No G&J reference, reductions, restrictions, uncited reduction on June 17, 2014 by Sean T. McCulloch.

Post navigation

Newer posts →

Search for: