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
12 views

What are the known NP-hardness or optimization results about spectrum of matrices? [on hold]

Like for symmetric $d-$regular matrices over 0/1 or 0/1/-1 what are some known optimization results about their possible spectral radius or spectral gap? [..I am calling a symmetric matrix to be ...
1
vote
1answer
14 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
51 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
36 views

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

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
42 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
80 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
54 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
47 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
71 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
119 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
38 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
51 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
48 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
106 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
44 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
26 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 ...
-2
votes
0answers
15 views

Negative Cost Cycle in a Directed Network [duplicate]

Does anyone have a code for finding the negative cost cycles in a directed network? Or can help how to find one? The problem is to generate an arbitrary network with random arc costs, and then find a ...
-3
votes
0answers
37 views

Diameter and some Formula on Graph Theory

in an undirected graph G, we define: Diameter is maximum of minimum paths between two vertex of a graph. L(s) is maximum length of minimum paths from s to ...
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
75 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
111 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
46 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
82 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
31 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
93 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
104 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
139 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
31 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
60 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 ...
3
votes
1answer
105 views

Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ ...
4
votes
0answers
35 views

Parallel algorithm to find if a set of nodes is on an elememtry cycle in a directed/undirected graph

I'm looking to find / develop a simple parallel algorithm that does this: Input: vs: list of root vertices max_length: max cycle length max_dist: max distance to root Variants one variant of ...
5
votes
1answer
107 views

Subgraph isomorphism in planar graphs

I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs. I'm trying to find subgraph matches to map an application graph (the subgraph) to a ...
0
votes
1answer
25 views

Update all nodes in a graph in a way that at any step all chosen nodes are disconnected

There are N nodes in a graph and some of them are connected with edges. All nodes are of type T1. The goal is to update all nodes to type T2. At any step you can choose any set of nodes and change ...
1
vote
2answers
58 views

Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...
4
votes
0answers
101 views

Suurballe's Algorithm: Proof of Correctness

I was reading about Suurballe's algorithm on Wikipedia, for the shortest edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight ...
2
votes
2answers
842 views

Is there an algorithm to find all the shortest paths between two nodes?

Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes. What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all ...
2
votes
0answers
23 views

Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their ...
3
votes
3answers
68 views

Why Iterative-Deepening-DFS requires O(b*d) memory?

After reading about iterative deepening depth-first search on Wikipedia, I could understand that it just limits the depth upto which dfs can go in one iteration/call. However, I could not understand ...