Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

learn more… | top users | synonyms (1)

0
votes
0answers
5 views

Normalizing edge weights and the effect on Dijkstra's algorithm

If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would ...
0
votes
2answers
31 views

Computing theory: can a single node be a subgraph?

Can a single node be considered a subgraph? For example, if I had this graph, G: X-----Y and I deleted Y, leaving me with ...
1
vote
0answers
18 views

Weighted, Acyclic Graph and Change Weights Problem?

I ran into a question as follows: We have a Code on Weighted, Acyclic Graph G(V, E) with positive and negative edges. we change the weight of this graph with ...
4
votes
0answers
38 views

Recoloring bipartite graphs

Given a bipartite graph where every vertex is colored either red or blue I am trying to minimize the number of blue vertices, subject to a few constraints: I am only allowed to directly change the ...
2
votes
0answers
12 views

The set of all vertices, such that each vertex in the set has a path to exactly $k$ vertices

I need to find algorithms for both undirected and directed graphs, with no assumption on them being connected. Also the algorithms must be $O(V+E)$, where the undirected one should not depend on $k$. ...
0
votes
1answer
47 views

NP-Completeness - Reducing CLIQUE

Given a graph $G$, and integers $c$ and $k$, a group $X$ is a set of nodes $v_1, v_2, \dots, v_{|X|}$ that each have degree at least $c$ and that form a complete subgraph of $G$. Following decision ...
1
vote
1answer
18 views

Is a subgraph either a spanning subgraph or a full subgraph?

A graph $G' = (N' ,A')$ is a spanning subgraph of a graph $G = (N, A)$ iff $N ' = N$ and $A' \subseteq A$. A graph $G' = (N',A')$ is a full subgraph of a graph $G = (N, A)$ iff $N' ...
-3
votes
0answers
19 views

DFS and BFS sequence [on hold]

depth first search sequence started from vertex A=ABEDHIFCGJ breadth first search sequence started from vertex A=ABDEFIHCGJ am i correct?
6
votes
2answers
105 views

Maximize distance between k nodes in a graph

I have an undirected unweighted graph $G$ and I want to select $k$ nodes from $G$ such that they are pairwise as far as possible from each other, in terms of geodesic distance. In other words they ...
5
votes
1answer
97 views

Tree decomposition - Fastest algorithm in practise

I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph. I found the paper "A linear time algorithm for finding tree-decompositions of ...
-3
votes
0answers
15 views

Post Order Analysis (Quick Check) [closed]

Left subtree, right subtree, then root. This is my understanding B J D N P M K R W Y T Q Is this correct?
-1
votes
1answer
50 views

Maximum edges in degree-restricted digraph

How many edges can there be in a loop-free, asymmetric $n$-vertex digraph, if each node can have maximum total degree $k$ and minimum total degree $m$? That is, There are no edges $(v,v)$ ...
1
vote
1answer
19 views

Solving cycle in undirected graph in log space?

Setting Let: $$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$ My Solution we show $UCYLE \in L$ by constructing $\mathcal M$ that decides ...
-1
votes
0answers
26 views

Prove correctness of algorithm - how to show the properties

Give an algorithm that finds the MST (maximum spanning tree) of a graph G=(V,E). Prove that the algorithm you gave finds the MST. I tried the following: I applied the Kruskal algorithm, but ...
1
vote
2answers
70 views

Reachability matrix in time $O(|V| \cdot |E|)$

Suppose that we are given a directed graph and we want to find out if a vertex $j$ is reachable from another vertex $i$ for all vertex pairs $(i, j)$ in the given graph. Reachable mean that there is a ...
1
vote
0answers
29 views

Terminology for a graph with ports on its nodes

A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain ...
-1
votes
1answer
40 views

C program - Visually display Graph and checking for Hamiltonian Paths? [closed]

I have a very large graph in my c program with a list of nodes and edges. I want to print out the visual representation of this. What is the best way to go about this? Additionally what's the best ...
1
vote
1answer
45 views

Practical applications of Weighted Independent Set in path graph?

Consider Weighted Independent Set in a path graph, i.e., a graph where all the vertices are in a single path. Does this problem have practical applications? What are some? This problem is used in ...
1
vote
1answer
92 views

Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph

I have been scratching my head to find good counter examples to the following problem: Suppose we are given a directed graph G=(V,E) in which every edge has a distinct positive edge weight. A ...
2
votes
1answer
55 views

Shortest paths in weighted graphs, and minimum spanning trees

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
5
votes
1answer
49 views

Polynomial time algorithm for finding two or more vertex-disjoint cycles

The cycle detection problem for a directed graph has well-known polynomial time solutions, graph traversal algorithms such as Dijkstra algorithm can be used to find whether or not a cycle exists in a ...
2
votes
1answer
74 views

Lowest Common Ancestor from children up?

I've seen algorithms for finding the lowest common ancestor from the root of a tree. However, I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom ...
-1
votes
1answer
123 views

Approximating the diameter of graph G

Anyone has an idea how to solve this problem: Let G be an undirected, unit-weighted connected graph. Design a linear-time algorithm to obtain a 2-approximation of the diameter of G. I.e., the largest ...
0
votes
0answers
20 views

Graph Centrality: spectral techniques

What is the difference between: normalizing the row of an adjacency matrix and taking the right eigenvector normalizing the row of an adjacency matrix and taking the left eigenvector normalizing the ...
4
votes
1answer
39 views

Finding the interior of a connected graph

I'm designing software that produces images such as the following: Regions of interest are circumscribed by red pixels. I am interested in extracting the fully-enclosed pixel regions. Ultimately, I ...
1
vote
0answers
28 views

Distance Largest Weight Edge in MST

Given a set $P$ of $k$ points in a plane. The Distance Variant problem: partition set $P$ into two subsets $P_{1}, P_{2}$ so you can maximize, $d(P_{1}, P_{2})$ = min $p \in P_{1}$ min $ q \in ...
0
votes
1answer
14 views

Number of path with given length within an unrooted Tree

Given a Tree (without a root) function w : v -> N and a number C - How can we count the number of verticies with distance between them equal to C. I was thinking about some smart vertice numbering so ...
5
votes
1answer
104 views

Reduction from Vertex Cover to Polygon Cover

Polygon Cover: Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$. Output: True if and only if there exists a subset in $S$ of at most $k$ ...
3
votes
1answer
54 views

Algorithm to extract the subgraph of all nodes with degree at least four

I have an undirected graph represented by a list of nodes and a list of edges. What I need to produce from this is a list of nodes and edges representing a new graph containing only the nodes which ...
0
votes
1answer
49 views

How do you search a graph? [closed]

An interview question I was asked. I was first asked how to traverse a graph and next I was asked how to search one. Got the first one but not the second. What is the modern standard way to search ...
1
vote
0answers
31 views

Fully dynamic k-shortest-path

Problem: My graph is a directed acyclic graph with positive edge weights. It is constantly changing in that nodes are deleted and added. For each change, I need to find the k-shortest-path. My ...
4
votes
1answer
111 views

Bellman-Ford Termination when there is no change on vertex weights?

We know the bellman-ford algorithms check all edges in each step, and for each edge if, d(v)>d(u)+w(u,v) then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the ...
3
votes
1answer
45 views

Understanding terms related to 2SAT algorithm [closed]

Recently I am learning about solution of the 2-satiability problem using strongly connected components. There is a theorem related to this problem given below: Let $F = Q_lx_1 Q_2x_2\ldots Q_nx_n C$ ...
2
votes
1answer
28 views

Explanation of implementation of an algorithm for Dominating Set [closed]

I'm working on an application, in which users can use domination in graphs. I have already finished up with graph generation algorithm, I use lists to store vertices... So, I have found a well ...
-1
votes
1answer
47 views

Comparing two graphs, finding vertices that changed their positions

I have a task of comparing two organisation charts. These chart objects are described as a set of nodes (people) where each has a unique ID field and a parent ID field (pointing to another node's ...
3
votes
1answer
70 views

Is a “tree” with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree?

For the following $2$ cases: (1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all) (2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$) Are they considered a valid tree? It seems ...
2
votes
3answers
76 views

Graph cycles on 40 vertices

I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language. The language specifies that a graph is only part of this language if it has a cycle on 40 ...
4
votes
1answer
112 views

Finding all circuits that contain a given edge

Given a directed graph $G = (V, E)$ and an edge $e \in E$, I'm trying to come up with an algorithm to construct the minimum induced subgraph $H$ of $G$ with the property that every circuit in $G$ that ...
1
vote
2answers
45 views

Spanning tree with chosen leaves

I'm working on the following problem: Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find the ...
0
votes
1answer
61 views

Is it possible to convert a graph with one negative capacity to a graph with only positive capacities?

I am interested in whether a graph (say, a complete graph) with one capacity negative (or many, but one should suffice) can be reconstructed as a graph with all non-negative capacities where the max ...
2
votes
1answer
47 views

Kosaraju's algorithm's time complexity

I've reading up on Kosaraju's algorithm to compute the strongly connected components of a directed graph and I found that using an adjacency list representation gives a time complexity of ...
0
votes
1answer
39 views

undirected graph without weights and DFS [closed]

following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times. check that G is ...
3
votes
1answer
83 views

Shortest path in a mutable graph

I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find any shortest path to every other node from a root $s$. This is performed in time proportional to ...
0
votes
0answers
32 views

Finding Contextual Nodes in a Knowledge Graph

I'm currently participating in developing a knowledge graph that uses ConceptNet and a few others as its data sources. It uses the same architecture as ConceptNet namely it is stored as a hypergraph ...
0
votes
2answers
94 views

Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$ [closed]

I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a ...
3
votes
1answer
108 views

Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

I'm trying to reproduce the synthetic networks (graphs) described in some papers. The topic is the same as a previous question of mine, but with a different focus. It is stated that the Erdos-Renyi ...
5
votes
1answer
154 views

Generate scale-free networks with power-law degree distributions using Barabasi-Albert

I'm trying to reproduce the synthetic networks (graphs) described in some papers. It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree ...
5
votes
2answers
45 views

Algorithm to generate all planar graphs

Is there an algorithm which provides a sequence of all simple planar graphs, unique by graph isomorphism? For instance: first all planar graphs with 1 node, then all planar graphs with 2 nodes, etc. ...
0
votes
0answers
32 views

Designing a turing machine to determine if there is path from two vertices in a directed graph or not

I'm self studying automata and I'm in chapter 7 of Sipser book. I want to design a diagram for a Turing machine that shows if there is path from s to t in a directed graph. My tape is like this: ...
6
votes
1answer
64 views

Finding a maximal independent set in parallel

On a graph $G(V,E)$, we do the following process: Initially, all nodes in $V$ are uncolored. While there are uncolored nodes in $V$, each uncolored node does the following: Selects a random real ...