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
1answer
22 views

Minimal hypergraph transversals

the exact complexity for hypergraph transversal problem is yet unknown and is an open research problem. However, I would need a fast way to compute, on paper, the minimal transversal of a hypergraph. ...
0
votes
1answer
47 views

Deep DFS traverse on graph

First, the question is based on http://stackoverflow.com/questions/2893470. By chess rules, the (undirected) graph generated from the above problem is the following: $$ \begin{array}{ccccc} 3 &...
0
votes
0answers
21 views

Longest path in graph with SQL [closed]

How can I find the longest paths in graph between two nodes using SQL? I've two table each for nodes and edges. Edge table contains from-to-weight.
-1
votes
0answers
36 views

Power graph analysis/visualization implementation? [closed]

Is there any document or paper with enough details to implement power graph analysis/visualization or any open-source implementation of it?
1
vote
0answers
25 views

Maximal Independent Set [closed]

Regarding algorithms to find maximal independent set in an unweighted and undirected graph: I saw many articles online that are referring to the case of which every vertex has a maximal degree of d, ...
1
vote
1answer
36 views

Label coloring to maximize number of “balanced” triangles (NP-hardness)

Define a triangle in undirected graph $G$ is balanced if the edge labels in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory). Problem ...
0
votes
0answers
52 views

Understanding Chazelle's bin packing algorithm

I'm having trouble understanding Chazelle's algorithm ,which is discussed in this paper The bottom-left bin-packing heuristic: an efficient implementation by B. Chazelle (1983), especially in ...
-3
votes
0answers
14 views

Why DFS that is processed by stack is showing wrong sequence [closed]

See DFS image Here I am using stack to print sequence of dfs. According to input and that image of graph, sequence is 1 2 4 8 5 6 3 7 . But My code is giving output as 1 2 4 8 7 6 5 3 . Can anyone ...
2
votes
1answer
41 views

why & how are BFS nodes goal tested when they are generated?

In BFS, nodes are goal tested when they are generated.In other searches, nodes are goal tested before expanding them.what is the difference between this two statements? What is the advantage from this?...
6
votes
1answer
83 views

Time complexity of Depth First Search

Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about. I ...
0
votes
0answers
64 views

Non-convex optimization problem over graphs

Given integers $m,n$, I want to compute the maximum possible value of $\Phi(G)$, over all simple, connected, undirected, unweighted graphs $G$ with $n$ vertices and $m$ edges. The objective function $...
-1
votes
1answer
40 views

DFS for all possible walks from a source to a destination with exactly k edges

Problem Statement: Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk. My question is that, say we have a DAG (...
4
votes
1answer
24 views

Is the inverse of MST cycle property always true? Why?

I am trying to find an algorithm which would check for each edge in a given weighted undirected graph whether it belongs to any of the graph's Minimum Spanning Trees. I have found many potential ...
3
votes
0answers
56 views

Early termination of A* with weak heuristic if solution is known

I have a large graph G and a pair of nodes s,t. I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent. Suppose I already know of a path ...
3
votes
1answer
25 views

Efficient algorithm for graph canonization for directed acyclic graphs?

I'm interesting in generating directed acyclic graphs (see here, for example). As part of this search, I'm curious if there are any efficient algorithms for determining a canonization of a directed ...
2
votes
0answers
13 views

Orderly graph generation and graph canonization confusion

In Orderly algorithms for generating restricted classes of graphs, Colbourn and Read expand on the earlier introduction of the orderly generation of graphs. Briefly, orderly generation allows you to ...
4
votes
0answers
28 views

Parallel bubble sorting on arbitrary graphs

Are there bubblesort-esque algorithms for sorting on arbitrary graphs? I'm working on a problem in which $k$ robots are placed randomly on a graph and have to reach their respective goals as quickly ...
6
votes
1answer
179 views

When is the minimum spanning tree for a graph not unique

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G? I know that the MST is unique when all of the weights are distinct, but ...
1
vote
1answer
63 views

Which neural network topology is the most efficient to generate randomly shaped letters?

I have created some unique shapes, so-called "letters" for a custom alphabet, all of which can fit into 9x9 pixels. Instead of drawing countless more, I try to combine two solutions I saw in a ...
3
votes
1answer
77 views

Find all cycles through a given vertex

Given a directed graph $G$ and a vertex $v$, how can we enumerate all simple cycles that pass through $v$? I found a question that describes how to enumerate all simple cycles in $G$, but I want only ...
1
vote
0answers
79 views

Given a directed graph and a vertex v, find all cycles that go through v? [duplicate]

Given a set of uniquely numbered items that each has three attributes id, from and two in ...
2
votes
1answer
46 views

Linear time algorithm for finding $k$ shortest paths in unweighted graphs

Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the ...
6
votes
1answer
90 views

Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the length of ...
-3
votes
0answers
32 views

Is that the way of Proving or disproving MST? [duplicate]

I need help with prove/disprove this : if G= (V; E) be an undirected graph (unweighted). Prove or disprove : the minimum spanning tree T formed by Kruskal's algorithm also provides a minimum ...
1
vote
1answer
49 views

Dijkstra's algorithm runtime for dense graphs

The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is $O((E+V)\log V)$. For a dense graph such as a complete graph, there can be $V(V-1)/2$ edges. Since $E \sim ...
1
vote
1answer
86 views

Problems that are easy on bipartite but hard on general graphs

Are there any problems that are easy for bipartite graphs, but hard for general graphs? I am asking because some classical problems are formulated in reference to people looking for a spouse, such as ...
0
votes
0answers
33 views

RMAT graph generator : Expected number of nodes with degree k?

I read this paper "R-MAT: A Recursive Model for Graph Mining" by Deepayan Chakrabarti ( In SDM. Vol. 4. 2004)(http://repository.cmu.edu/cgi/viewcontent.cgi?article=1541&context=compsci) from cmu ...
0
votes
0answers
36 views

Fastest Algorithm to find shortest path between two edges in a graph

If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)? I am trying to answer a question in the EPI book. ...
0
votes
1answer
73 views

Understanding The Mapping Of Edges to Nodes In A Graph Theory Problem

I am really confused with this problem. Here's the problem: You have $N$ points numbered $1$ through $N$,inclusive, and $N$ arrows again numbered $1$ through $N$,inclusive. No two arrows start at ...
-3
votes
0answers
23 views

Find orientation graph of undirected graph that mimimizes absolute difference of in-degree and out degree

Here's a question from our uni's ICPC programming competition selections. I'm stating it in simpler terms here. Given an undirected graph, orient the edges of the graph in such a manner that the ...
0
votes
0answers
24 views

Is maximum size of graph matching equal to maximum size of its dual graph matching?

This is really puzzling me! A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$. A ...
0
votes
1answer
87 views

Cluster Edge Deletion on 2-trees [closed]

Definitions: Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced ...
1
vote
3answers
41 views

More efficient vertex-labelling algorithm than BFS?

I am using the C++ boost library implementation of the push relabel algorithm to solve a max-flow problem. The output from that algorithm is a residual graph and in order to find the min-cut of my ...
4
votes
2answers
101 views

Dijkstra with bitwise OR of edge costs

Given a graph $G$ where loops and multiple edges are allowed. A path {$e_1, e_2, ..., e_k$} (a sequence of edges) has a cost $$ cost = e_1 | e_2 |...|e_k$$ where $|$ is the bitwise OR. Assume for all ...
0
votes
0answers
37 views

Compression of a complete Directed Acylcic Graph

Consider a DAG $g$ as a label $l$ with a list of sub-nodes $\bar{g}$: $g ::= l \enspace \bar{g}$ This is an "unfolded" representation of the DAG, i.e. it contains double entries, when two paths ...
0
votes
0answers
34 views

Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
2
votes
0answers
24 views

Powerlaw graphs : Number of hubs and fraction of edges incident on them

As per the definition of power law, the fraction P(k) of nodes with k degree for large values of k , given by P(k) ~k ^-r . In this definition, the term large value is not clearly defined. Does ...
3
votes
0answers
56 views

Orient edges in a mixed graph to minimize the critical path

A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way that no cycle is ...
2
votes
2answers
137 views

Computing maximum-cost subtree that uses at most k edges

I'm looking for an efficient algorithm for the following problem: Input: a binary, complete tree with a cost on each edge, an integer $k$ Output: the maximum-cost subtree containing $\le k$ edges ...
3
votes
1answer
41 views

Single-source shortest path algorithm for graphs representing stacked behavior

I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG). That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent ...
3
votes
0answers
43 views

Can we create the level graph from sink to source in Dinitz?

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS. Could we create the level graph from sink to source ...
0
votes
0answers
48 views

Checking for 4-cycles in a graph

I was reviewing some selected problems on algorithms and time complexity and the notes had the following exercise (ex. 4.3 from book Algorithms by Dasgupta, Vazirani, Papadimitriou): Design and ...
0
votes
0answers
34 views

Complete set of basic circuits for McLane's Theorem

I was assigned a project in which i had to implement some algorithms concerning graphs. The last one is the one described in the title. I have to make an algorithm that uses McLane's theorem (https://...
3
votes
1answer
58 views

Counting specific subgraphs

For a given undirected graph G, I want to count all the subgraphs H that satisfies the following conditions: H.V = G.V (The subgraph will containt all the original graph nodes) H is connected (...
0
votes
1answer
44 views

Is finding all cycles in a graph using some version of Johnson's algorithm (code provided) really polynomial (benchmark provided)?

This is the algorithm I'm using: http://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627#14115627 Specifically C#, but the linked thread has numerous languages. ...
0
votes
0answers
17 views

Is there a minimum spanning tree including $e$ after removing at most $k$ edges?

Let an undirected, connected graph $G=(V,E)$ with the weight funciton $w:E\to \mathbb{R}$, an edge $e$, and $0<k\in\mathbb{N}$. Describe an algorithm determines if there are at most $k$ edges could ...
0
votes
1answer
10 views

What is the difference in 'logical array blocked' and array list B, and what do they represent?

In Johnson's 1975 Paper 'Finding All the Elementary Circuits of a Directed Graph', his psuedocode refers to two separate data structures, logical array blocked and list array B. What is the difference ...
1
vote
1answer
53 views

Why is bipartite graph matching hard?

I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me ...
0
votes
0answers
26 views

Uniform generation of random bipartite bi-regular graphs?

I want an algorithm that takes the following Input: $M,N,k,d$ positive integers such that $kM = dN$. and produces the following Output: Random bipartite graph, with $M$ vertices all of degree $k$ ...
1
vote
0answers
19 views

How to make LALR(1) directly?

I studied LR(1) parsers and then LALR(1) and noticed that if we wanna construct LALR(1), We should FIRST construct the LR(1) parser and then by combining states we can go ahead for LALR(1) parser. ...