Tweeted twitter.com/StackCompSci/status/1096741003879424005
5 added 505 characters in body
source | link

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use Farach-Colton and Bender algorithm to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

Also, for the reference, there’s $O(n \log n)$ approach to solve this task, which doesn’t seem to be optimizable. Let’s store in the vertice the count of all vertices of each color (now the edge is separator if in subtree there’re either no occurrences, or all occurrences of each color), but it’s a quadratic solution. Now we use small-to-large approach (merge these arrays to the one that belongs to the largest child, and pass the reference to that array to the parent), and it becomes $O(n \log n)$.

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use Farach-Colton and Bender algorithm to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use Farach-Colton and Bender algorithm to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

Also, for the reference, there’s $O(n \log n)$ approach to solve this task, which doesn’t seem to be optimizable. Let’s store in the vertice the count of all vertices of each color (now the edge is separator if in subtree there’re either no occurrences, or all occurrences of each color), but it’s a quadratic solution. Now we use small-to-large approach (merge these arrays to the one that belongs to the largest child, and pass the reference to that array to the parent), and it becomes $O(n \log n)$.

4 added 31 characters in body
source | link

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use FCBFarach-Colton and Bender algorithm to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use FCB to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use Farach-Colton and Bender algorithm to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

3 added 22 characters in body; edited title
source | link

Find all separatorsedges in a tree whose removal doesn't separate color classes

Given a tree of N$N$ vertices, each colored in one of the colors 1...N$1,\dots,N$.

Let’s call an edge a separatorseparator if when suchthe edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in O(N)$O(N)$ time and O(N)$O(N)$ memory.

My first approach was to use FCB to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some verticevertex of the same color for any color, but I can’t come up with any ideas to move further.

Find all separators in a tree

Given a tree of N vertices, each colored in one of colors 1...N.

Let’s call an edge a separator if when such edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in O(N) time and O(N) memory.

My first approach was to use FCB to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertice of the same color for any color, but I can’t come up with any ideas to move further.

Find all edges in a tree whose removal doesn't separate color classes

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.

Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.

The goal is to find all separators in a tree in $O(N)$ time and $O(N)$ memory.

My first approach was to use FCB to find LCA of all vertices of each color, and then the separator is an edge that doesn’t lie on a path between the LCA and some vertex of the same color for any color, but I can’t come up with any ideas to move further.

2 edited body
source | link
1
source | link