Skip to main content
Computer Science

Return to Question

replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link
Community Bot
Community Bot
  • 1

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see thisthis answer at SO.

My question: above problem is in $P$?

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?

Tweeted twitter.com/#!/StackCompSci/status/337749328095506435
added 41 characters in body
Source Link
user742
user742

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?

Source Link
user742
user742

Longest path in grid like graph

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.