Skip to main content
Computer Science

Return to Question

Rollback to Revision 2
Source Link
Juho
Juho
  • 22.8k
  • 7
  • 62
  • 117

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice.

Is the problem of determining whether a graph is almost Hamiltonian NP-complete?

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice.

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice.

Is the problem of determining whether a graph is almost Hamiltonian NP-complete?

deleted 80 characters in body; edited tags
Source Link
user15531
user15531

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice.

Is the problem of determining whether a graph is almost Hamiltonian NP-complete?

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice.

Is the problem of determining whether a graph is almost Hamiltonian NP-complete?

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice.

Tweeted twitter.com/StackCompSci/status/655075030368415744
Separated the question into a definition and a question.
Source Link
Dave Clarke
Dave Clarke
  • 20.3k
  • 4
  • 68
  • 113

Is it possible to show that if aA graph that is almost Hamiltonian withalmost Hamiltonian if it contains a cycle that containsvisits every node of it at least once and at most twice as.

Is the problem of determining whether a graph is almost Hamiltonian NP-complete problem?

Is it possible to show that if a graph that is almost Hamiltonian with a cycle that contains every node of it at least once and at most twice as NP-complete problem?

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice.

Is the problem of determining whether a graph is almost Hamiltonian NP-complete?

Source Link
user15531
user15531