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)

1
vote
0answers
7 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
32 views

Shortest Path problem(Single Source&Destination)

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 ...
3
votes
0answers
32 views

Directed acyclic graphs and Latin Squares

Every Latin square corresponds to a directed acyclic graph with a lattice arrangement, and whose edges indicate label order (<). For example: I'm interested ...
0
votes
0answers
34 views

Can any program be represented through graph theory?

So my understanding is that each variable in a program could be represented as a node which feeds into other nodes which use the variable nodes to produce a result (functions). And you can define the ...
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))$ ...
-2
votes
0answers
69 views

Find the city that is farthest away from its nearest police station

It is given an undirected graph $G = (V, E)$ and a weight function $w : E \rightarrow\mathbb{Z} ^{+}$, which we interpret as distance between vertices. The vertices of the graph are cities, and in ...
0
votes
0answers
23 views

State of art algos for triangulating graphs and finding the maximal cliques [closed]

I am currently working on an application of triangulation on a given moral graph and then finding the maximal cliques. So, I would like to know any well written papers and the state of art algorithms ...
3
votes
0answers
34 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 ...
0
votes
2answers
87 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
100 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
63 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
13 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
80 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 ...
0
votes
1answer
23 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
15 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
51 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 ...
0
votes
1answer
55 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
50 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
44 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
29 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
54 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
58 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
18 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
17 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
57 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
42 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
41 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
26 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 ...
3
votes
1answer
20 views

n-polygon lattice datastructure?

I'm trying to simulate a boardgame what can be played on a board with an arbitrary lattice, anything from triangles to heptagons to 37-sided regular polygons is allowed. Moreover the shape of the ...
1
vote
1answer
30 views

Decreasing a digraph's edge-weights while keeping net weights of edges at each vertex constant

Given a directed weighted graph, is there an algorithm that does the following: Removes as many edges possible. Reduces as many weights as possible. Given the constraint that the net weight of all ...
0
votes
0answers
27 views

Is there a fast, “partial planarization” algorithm for non-planar graphs?

On "partial planarization" I understand an algorithm, which tries to reach a optimal, or nearly-optimal solution for non-planar graphs. For example, which minimizes the number of the crossing edges ...
0
votes
1answer
18 views

Multiple of Hamiltonian Cycles

I'm currently confused whether a graph should contain strictly one distinct Hamiltonian Cycle. (given that [1,2,3,4,1] and [2,3,4,1,2] are the same). I was wondering if, by definition, there can be ...
-1
votes
1answer
38 views

Best pathfinding algorithm for undirected unweighted graph [closed]

I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the ...
2
votes
1answer
38 views

Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization

I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any inaccuracies. Happy to clarify any part of the question which is unclear. Given the following ...
2
votes
1answer
34 views

Counting the nodes in a network in a distributed way

There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters). One of the nodes, say $s$, wants to know $n$. How can it do ...
1
vote
1answer
13 views

Confusion regarding DAGs

I've a question regarding DAGs. My instructor asked me to prove that strongly connected component of a DAG is also a DAG. I don't get it. How can a graph be DAG and strongly connected at the same ...
0
votes
0answers
25 views

Finding the second lightest path in a graph

Assume I have a weighted, directional graph with no cycles. What is the most efficient way to find the second lightest path from the source vertex to a given vertex?
0
votes
0answers
27 views

Running the Double Tree Heuristic in a given graph - some slight confusion

I'm working on an exam question that asks me to run the Double-Tree Heuristic algorithm on the following graph: This algorithm starts by finding a minimum cost spanning tree. My solution: ...
0
votes
0answers
23 views

Measure of network branchiness on a weighted graph

I'm working with road networks, in which each edge is a physical street segment with a length attribute. Nodes represent junctions. However, my question should be generalizable to any weighted graph. ...
1
vote
1answer
22 views

Why is one traversal sufficient for the Kuhn's maximal matching problem algorithm?

In Kuhn's algorithm for the maximum bipartite matching problem we iterate through the vertices of one partite set and try to build the increasing chain, starting with the current vertex. Once the ...
1
vote
1answer
26 views

How do you produce a CNF from a circular graph with colouring?

If you had a circular graph e.g. A->B->C->D->E->A, and a legal coloring system with 3 colours (e.g. Red, Green Blue), where each node is assigned a colour and no node can be connected to another node ...
0
votes
1answer
39 views

Can I find a clique with more than 2 nodes in a bipartite graph?

As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?