Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

learn more… | top users | synonyms

2
votes
2answers
37 views

What is the intuition on why the longest path problem does not have optimal substructure?

I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think ...
1
vote
1answer
36 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ vertices and $M$ edges. Each edge has its own weight and colour. There are at most 10 different colours in the whole graph. Each time I traverse edges of ...
3
votes
0answers
29 views

Vertex Disjoint Path Covers of Hypercube-Like Graphs

This is a followup question relating to an older question I posted, namely: Decomposing the n-cube into vertex-disjoint paths. Given a graph $G = (V, E)$ and sets of distinct vertices $S = \{s_1, ...
-4
votes
1answer
59 views

Proving a problem is in P?

Problem: A square in an undirected graph is a cycle of length 4, i.e. four vertices that form a cycle. Show that the problem: ...
0
votes
0answers
6 views

Should all internal node keys in B+ tree also be in the leaves?

I was reading about B+ tree insertion. The algorithm takes following form: Insert the new node as the leaf node. If the leaf node overflows, split the node and copy the middle element to the ...
1
vote
2answers
37 views

Is there a name for graphs which contain oriented and non-oriented edges?

Is there a name for graphs which contain oriented and non-oriented edges? I couldn't find on the internet if there exist a specific name for such graphs.
1
vote
1answer
42 views

Algorithm to find a path connecting given nodes in a graph

Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for ...
0
votes
1answer
28 views

Facts about internal and external path lengths of binary tree

While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some ...
1
vote
1answer
36 views

What does a ball of center v and radius r with at most r hops away mean?

I am trying to understand what that sentence means. Intuitively, its obvious a radius ball means in a $ \mathbb{R}^{n}$ with respect to some norm. Its just the following set: $$ B(v, r) = \{ x \in ...
-3
votes
0answers
18 views

Prüfer decoding program doesn't work [closed]

Please, could you tell me what's wrong with this program that deals with Prüfer decoding? ...
-1
votes
0answers
14 views

What is the difference between K-array tree and Binary search tree. [on hold]

Want to know the difference between K-array and Binary search tree.
0
votes
1answer
26 views

Can an independent set (of vertices) be a vertex cover as well?

I wanted to clarify if this is possible, so I thought about a possible vertex cover that can also serve as an independent set: So, to clarify, am I right to say that the nodes in red are both (i) a ...
0
votes
1answer
21 views

Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

Given the theorem that max flow <= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?
2
votes
1answer
53 views
+100

Find all non-isomorphic graphs with a particular degree sequence

I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible. The only way I found is generating the first graph using the Havel-Hakimi ...
6
votes
0answers
120 views

How to solve the loan graph problem

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
0
votes
0answers
40 views

Find closed loops in an undirected graph given an adjacency list

I am trying to find all the cycles in an undirected graph given the adjacency list of the vertices, with the an output of all the cycles in form of the vertices they are made up of. For example ...
0
votes
1answer
18 views

Check Cycles- On adding an edge in DAG

Given a DAG N, if an edge $(U \rightarrow V)$ is added between any existing nodes U and V. Then, by performing DFS from the node $U$ and checking whether there is a cycle or a not, should be ...
-1
votes
3answers
89 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
2
votes
1answer
27 views

Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2

I stumbled upon the following problem during my research. I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting ...
4
votes
1answer
37 views

Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to ...
1
vote
1answer
23 views

Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows: We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there ...
1
vote
1answer
55 views

Markov Chain Mixing Time of the Complete Graph

I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn). We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically ...
3
votes
1answer
77 views

How many number of different binary trees are possible for a given postorder (or preorder) traversal

I came across the problem: What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C? Now 3 being small number I was quick to draw all possible ...
0
votes
1answer
76 views

Is this a proof that SET COVER is not an NP-hard problem?

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows: Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = ...
0
votes
2answers
43 views

Induced subgraph problem in trees

Let $~G~$ be unweighted unordered tree. I have some number of pairs of this tree's vertices $~(u_1, v_1), \dots, (u_n, v_n)$. I need to construct a smallest subgraph of original tree such that for ...
3
votes
1answer
39 views

How to generate a degree sequence of a degree distribution

How to generate a degree sequence of a degree distribution that follows the power-law in which I know $N=10^2$ and $\gamma=2.5$? The degree distribution of power-law is $p_k \sim k^{-\gamma}$. I ...
1
vote
2answers
54 views

Which is more fundamental: key-value or subject-predicate-object?

There seems to be two approaches to store data in NoSQL databases: Key-Value - The Key is usually stored in a hash-table referencing a ...
2
votes
0answers
23 views

Maximum Weight Planarization of Size $n$ [duplicate]

Problem: Maximum Weight Planarization Given a weighted non-planar graph with $n$ vertices, and $m = \mathcal O\left(n^2\right)$ edges. Find the subgraph with $n$ nodes (but possibly removing edges ...
4
votes
1answer
60 views

Decomposing the n-cube into vertex-disjoint paths

I am not sure if this question is better suited for cs.stackexchange or math.stackexchange - This is of interested to me in the context of a data structure problem, but the question itself may be ...
2
votes
0answers
53 views

General Steiner Tree Variants

In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all ...
2
votes
1answer
46 views

Is the unweighted vertex cover problem equivalent to its weighted version?

Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq_\mathrm{m} ...
2
votes
0answers
41 views

Kleinberg Rubinfeld Short Paths in Expander Graphs for Hypergraphs [migrated]

In 96 Kleinberg and Rubinfeld in "short paths in expander graphs" showed that for any $\Delta$-regular $\alpha$-expander graph ($\alpha >0$) $G$ on $n$ nodes, if $H$ is any graph on at most $cn/ ...
1
vote
0answers
22 views

Finding one face in planar graph

Given a planar graph (represented using adjacency lists) we want to find a set of vertices which are around one (random) face. We know that the graph contains at least one triangle. How do we find ...
1
vote
1answer
32 views

Residual Graph in Maximum Flow

I am reading about the Maximum Flow Problem Here. I could not understand the initiation behind the Residual Graph. Why we are considering a back edge while calculating the flow. Can anyone help me in ...
0
votes
0answers
16 views

Linear and Non-linear data set in K-means algorithm

The site K-means says that the algorithm fails for a non-linear data set. What do you mean by a non-linear data set in clustering algorithms? How different is it from a linear-data set?
12
votes
4answers
342 views

Dijkstra's algorithm on huge graphs

I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to ...
2
votes
0answers
58 views

How to color sudoku with this added constraint?

I couldn't figure out an algorithm for following graph coloring problem: Output color of each vertex for this graph: Given a solved 9*9 sudoku board that is a 9-colored board, applied first three ...
3
votes
0answers
122 views

Online bipartite edge-cover problem with requirements

I have $N$ nodes $v_1,\ldots,v_N$ in one partition $X$ and $M \leq N$ nodes $u_1,\ldots,u_M$ in a different partition $Y$. I want to connect nodes in $X$ to nodes in $Y$ with edges under the following ...
1
vote
1answer
31 views

Algorithm for graph with nodes grouped into sets

I have a weighted graph. The nodes of this graph are grouped into sets, and each node has only one corresponding set (no overlapping). Nodes in the same set do not have edges between them. An edge ...
3
votes
1answer
124 views

Parameterized Dominating Set

What is the best algorithm to compute p-dominating set? The p-dominating set problem is a parameterized version of minimum dominating set in which the problem takes a parameter $k$ also as an input, ...
3
votes
2answers
159 views

Difference between graph-partitioning and graph-clustering

What is the difference between graph-partitioning and graph-clustering in graph theory?
1
vote
0answers
21 views

Difference between graph-partitioning and graph-coarsening

What is the difference between graph-partitioning and graph-coarsening with respect to scale-free networks? I am trying to analyze graphs generated using the data from social networks. Do both the ...
3
votes
1answer
24 views

Should planar Euclidean graphs be planar straight-line graphs?

An Euclidean graph, by definition is A weighted graph in which the weights are equal to the Euclidean lengths of the edges in a specified embedding and a graph is called planar if it can ...
0
votes
2answers
53 views

A Graph's Density and Sparsity

A graph is dense when |E| (edges) is closest to $|V|^2$. A graph is sparse when |E| is closer to $|V|$. What does it mean to take the magnitude of the vertices? Secondly, I am having a hard time ...
3
votes
1answer
26 views
6
votes
1answer
68 views

Vertex cover problem with 2-element vertices

Let $G = (W, E)$ be an undirected graph, where $W = \{(v_i,v_j) \in V \times V : v_i > v_j\}$ and $E$ is a set of $2$-element subsets of $W$ such that, given two edges $e_1 = (w_1, w_2)$ and $e_2 = ...
1
vote
1answer
133 views

A criterion for the planar graph to have unique dual

I get stuck with the following two criteria both about the uniqueness of plane embeddings of a given planar graph. The first one says that a planar graph admits unique plane embedding iff it is a ...
1
vote
1answer
16 views

Algorithm to find a subgraph such that all of its edges has an anti edge

Let $G=(V,E)$ be a directed graph. The "invertible" part of $G$ is the subgraph $H=(V,E_2)$ such that $(u,v)\in E_2 \iff (u,v)\in E \land (v,u)\in E$. Find an algorithm that generate $H$ from ...
-1
votes
1answer
16 views

Which tree decomposition of a graph is preferrable?

In this page, there are two examples of tree decomposition of a graph $G$. Could there be another decomposition such as: $\{A,B\}, \{C,E,F\}, \{D,F,G\}$ or did I get the rules of decomposition ...
2
votes
1answer
27 views

Approximating all independent sets of size k in a graph

Given an undirected graph, I need an algorithm that outputs all the independent sets of size >= k (constant) in the graph. I know the problem is NPC, and I do not want to use the exponential ...