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

Sort graph nodes by density [on hold]

Cyclic connected undirected graph. Every node in a graph has T value initially zero. Suppose there is a traverse via shortest path between every two nodes which increases every node's T value it ...
0
votes
0answers
35 views

Subgraph isomorphism by Ullman

I was trying to understand the subgraph isomorphism problem and I came across a slide http://oldwww.prip.tuwien.ac.at/teaching/ss/strupr/vogl.pdf In the 11'th page, the step by step description of M ...
0
votes
0answers
23 views

Algorithm for subgraph isomorphism [on hold]

Now I was reading up the paper of subgraph isomorphism by JR Ullman to understand the algorithm. Now I got the PDF and the algorithm looks like this: Now in step 2, what is after " if d=1 then" ? ...
0
votes
1answer
31 views

pseudo clique with at least connectivity x and maximum weight of the nodes

Let $G=(N,E)$ be a undirected graph of nodes $N$ and edges $E$. Each node $n \in N$ has a weight $w(n)$. The weight of a graph is defined as the sum of the weights of its nodes, i.e., by $w(G) = ...
2
votes
1answer
36 views

Proving algorithm for removing nodes from a complete graph with two kinds of edges

Lets say $G$ is complete undirected graph with a set of edges coloured either black or red. The problem is to find an algorithm answering if it is possible to remove a subset of nodes from $G$ in a ...
0
votes
2answers
43 views

Existence of shortest path in a graph with no negative cycles?

Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex. How do I prove that for every ...
4
votes
1answer
96 views

Unique path sums in a DAG using vertex instrumentation

I stumbled across this paper from Ball et al. In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control ...
0
votes
0answers
37 views

Possible Paths in Pipe Network

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit i have to ...
1
vote
1answer
41 views

Removing edges of a weighted graph

I have an edge weighted $N{\times}N$ graph and the edge similarity values are bound to $[0,1]$. What I am trying to do is to find a cut-off threshold below which I can say that that edges are noisy/ ...
2
votes
1answer
45 views

What is the graph with $8$ vertices and $12$ edges that has the most spanning trees? [closed]

I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?
0
votes
0answers
52 views

Find simple cycles pass through a vertex in drected graph

I want to find all the simple cycles with bounded length that pass through a vertex in a directed graph. Enumerating all the cycles in large graph takes exponential time. Since I need to find only the ...
1
vote
0answers
31 views

All paths of length n from a single graph vertex in a directed cyclic graph [duplicate]

Thanks in advance...looking for recommendations on an algorithm to find all paths of length n starting from a single node in a directed, cyclic graph. I am not concerned with at which node the path ...
2
votes
1answer
26 views

Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?

could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to ...
6
votes
2answers
87 views

Traversing a graph with respect to some partial order

Recently I was faced with the following Graph traversal problem: "Given an arrangement of buildings in form of a DAG. All the buildings have to be colored, but there is an order for that represented ...
2
votes
0answers
30 views

Packing the edges of a graph

Given a graph G, and positive integers k, q, pack the edges of G in (pairwise edge disjoint) connected sub-graphs, each of size (number of edges) at most k, and such that, no vertex is part of more ...
0
votes
1answer
41 views

Graph theory, $n$ people sitting around table [closed]

$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice. How big can $k$ be in terms of $n$? Does everybody get to sit next to everybody ...
4
votes
0answers
71 views

Computing the “at least k friends in common” graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
0
votes
0answers
27 views

Hierholzer's algorithm for finding Eulerian Path in Semi-directed multigraph [closed]

Background: There is an Android game called One Touch Drawing which is based on finding Eulerian Paths (or Circuits) in graphs. As the game progresses, there are several conditions introduced to ...
1
vote
1answer
37 views

SimRank on a weighted directed graph (how to calculate node similarity)

I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that ...
1
vote
1answer
44 views

Shortest Path problem(Single Source&Destination) [closed]

Given: A completely connected directed acyclic graph. What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes? Constraint: 1)The result ...
-1
votes
0answers
31 views

Reduction NP-Complete with graph undirected [duplicate]

Given a graph undirected $G=(V,E)$ a subset $I$ of $V$ is indipendent for each couples of vertices u,v in $I$ and {$u,v$} is not in $E$. Prove that the language $L$={$<G,k>$: $k$ is a positive ...
2
votes
1answer
24 views

Selecting k “special” nodes in a graph such that the min distance is maximized?

Lets say we have a graph $G$ with $|V|$ nodes. We wish to select $k$ such nodes while optimizing the following attribute: maximize: for each $i$ and $j$, where $i \neq j$, $min(distance(v_i, v_j))$ ...
3
votes
0answers
39 views

Voronoi Diagrams with L∞ Metric

I've recently become interested in randomly generating Voronoi diagrams to create "territory" maps (similar to this) for a project I've been working on. Traditional Voronoi diagrams using an ...
1
vote
2answers
116 views

Find all the paths from node A to node B

You are given a bunch of nodes evenly spaced in a rectangular shape. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand corner and node B is at the bottom right hand ...
9
votes
0answers
115 views

size of maximum matching in a bipartite graph

I've been wondering if there's a way to determine the size of a maximum matching in a non weighted bipartite graph without paying the full price of actually computing the matching itself. It's a long ...
1
vote
1answer
24 views

Enumerating connected subgraphs [closed]

Is there an efficient algorithm to visit/enumerate all unique connected subgraphs of a labelled graph? E.g., when the graph is a path, $v_1v_2\dots v_N$, there are $N(N-1)$ unique connected graphs: ...
1
vote
1answer
73 views

Computing the k shortest edge-disjoint paths on a weighted graph

Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty. We could use Dijkstra to find the 1st "disjoint" (edge ...
0
votes
1answer
15 views

Necessities for two undirected graphs being isomorphic

As far as I know, for two undirected graphs $G = (V, E) $ and $H = (V', E')$, the following criteria is necessary for them to be isomorphic: $|V| = |V'|$ $|E| = |E'|$ $G$ has $j$ nodes of degree $k$ ...
5
votes
0answers
58 views

Practical algorithms for the disjoint paths problem

Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from ...
3
votes
1answer
81 views

Locally finite graph without an optimal path

If I have a locally finite graph (every node has finite number of neighbors) with positive edge weights, is it possible for there to be a path between some start node and goal node but no shortest ...
1
vote
1answer
29 views

Select the n closest nodes from a starting node in a weighted directed graph

I need to select a given number of nodes from a weighted directed graph such that the nodes selected are the closest to a given starting node. This seems like a common problem to need to solve, but I ...
1
vote
1answer
37 views

How to get samples of different paths?

Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed). Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B. I ...
1
vote
1answer
28 views

For all nodes in a directed graph, find whether they are on a non trivial cycle (length > 2)

I'd like to find an efficient algorithm to answer this question: For each node in a directed graph, find whether it is on a non trivial cycle (length > 2) It sounds simple at first, but I still ...
1
vote
1answer
17 views

Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$ [duplicate]

For the graph colourability problem, we are given a graph and our goal is to find a colouring of the graph with the fewest possible number of colours so that no two adjacent vertices have the same ...
-1
votes
2answers
61 views

Why is T not a minimum spanning tree of G?

The Problem: Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.    a. True of ...
1
vote
1answer
57 views

How to draw a graph to disprove this statement?

The Problem: Indicate whether the following statements are true or false: a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum ...
1
vote
0answers
29 views

Minimum vertices to cover other vertices with max weight [duplicate]

I have a problem where I'm given the input of a graph. The output would be a set of vertices such that I have the minimum number of vertices to cover other vertices and if there is more than one ...
4
votes
1answer
51 views

How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of ...
0
votes
1answer
47 views

Parallel shortest path in directed acyclic graphs

Finding the shortest path in a DAG is extremely easy: See the example here http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf However, I cannot find a way of parallelising this code. Is ...
1
vote
0answers
45 views

Algorithm to split an ordered, undirected graph into subtrees? [closed]

I have an undirected graph, whose nodes have some sorting order defined on them. I have to split it into subgraphs such none of the subgraphs have any cycle. I am trying the following procedure ...
5
votes
0answers
31 views

Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
0
votes
1answer
55 views

Binary tree node value maximization

Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be ...
2
votes
1answer
61 views

Dijkstras Shortest Path with Distance and Quality [closed]

I want to write up a shortest as well as optimal path program for indoor navigation for people with disabilities. For the initial part of the assignment i wish to test my program through graph ...
0
votes
0answers
19 views

Minimum Augmenting pahts in Ford Fulkerson Algorithm

Based on the Ford Fulkerson method the choice of the next path to Augment is crucial so the algorithm can halt quickly. Is there any bound on the minimum number of paths that need to be "augmented" ...
-1
votes
1answer
18 views

Checking a property of all of the cycles in a graph

Suppose $G= (V,E)$ is a directed graph with weights on the edges. I would like to check if $G$ has the following property: if $C \subset E$ is the set of edges in a cycle of length at least $3$, then ...
0
votes
2answers
64 views

Counter example to graph coloring heuristic using BFS

I am considering the following heuristic for the graph coloring problem (i.e. to color a graph $G$ using a minimal number of colors so that no two adjacent vertices have the same color): Explore ...
1
vote
1answer
52 views

How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in a undirected graph?

How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in an undirected graph ? I've seen it stated that one can apply a maximum flow ...
2
votes
1answer
52 views

Efficiently enumerating all paths from i to j of given length in a graph

I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) ...
1
vote
1answer
48 views

Better algorithm for determining if a vertex is on any cycle in a graph

The problem I'm facing is the following: Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$. The algorithm I can think of is to remove an ...
0
votes
0answers
27 views

enumeration of all Maximal independent set on trees

what is the algorithm for enumerating all maximal independent set on trees (without the constaint of lexicographic order) . It 's very natural to find an algorithm faster than $ O(3^{n/3})$ on trees ...