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
votes
0answers
14 views

network flow approach for maximizing number of jobs that can be scheduled

I'm curious to lean the network-flow approach to solve this problem. Hope someone here can take time to help me construct an appropriate and suitable graph for this problem. The constructed graph, ...
0
votes
0answers
11 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
14 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
0answers
19 views

Counter example to graph coloring heuristic using BFS [on hold]

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 ...
2
votes
2answers
52 views

Path optimization in a DAG: maximizing number of least cost links

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
0
votes
0answers
16 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
37 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
46 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
24 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
19 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
20 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
25 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
17 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
34 views

Best pathfinding algorithm for undirected unweighted graph [on hold]

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
26 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
12 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
24 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
22 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
21 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
16 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
25 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
36 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?
1
vote
1answer
16 views

Is there any relation between Global minimum cut problem and Maximal independent set?

I have simple undirected graph. I want to determine a size of minimum vertex cover, a size of maximal independent set and a size ...
2
votes
1answer
36 views

Algorithm to find whether there is a path (any path) above length X between two vertices

We all know how to find the shortest path between two vertices, but what if I just want to know the answer to this question - is there a path, (any path), between vertex A and B of length larger than ...
0
votes
0answers
4 views

R ggplot How to place continuous x axis label under different facets [migrated]

Im plotting this graph in R ggplot2: ggplot(mplant, aes(x=Variant, y=value, fill=Infestation)) + geom_boxplot() + scale_fill_grey() + facet_wrap(~ variable, scales="free_y", ncol=2,) The problem ...
4
votes
0answers
35 views

Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper. We are talking about generating an undirected graph in a slightly different way ...
1
vote
1answer
22 views

An n-dimensional index where the search key specifies an exact match on certain dimensions?

I'm working on a project where I want to to search for vectors in the form (x1, x2, x3,...xn), and be able to search for them by specifying a specific x value and getting all vectors with that x value ...
0
votes
0answers
61 views

Can the Hamiltonian path problem be solved by dynamic programming in $O(2^n n)$ time?

Let G(V,E) be the graph and V = {$V_1$,$V_2$,....,$V_n$}. A dynamic programming approach solves the Hamiltonian path problem in $O(2^n n^3)$ time. We can have a matrix : dp[s][i][j] : which computes ...
2
votes
1answer
40 views

How to build a label flow graph for static analysis

I'm new to world of static analysis and am trying to build a new analysis of C programs for llvm compiler. I've started with the build of the graph of the constraints of the program: The edges ...
0
votes
1answer
42 views

Normalizing edge weights and the effect on Dijkstra's algorithm [duplicate]

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
54 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
71 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 ...
8
votes
2answers
141 views

Recoloring bipartite graphs

Given a bipartite graph $G = (A,B,E)$ where every vertex is colored either red or blue I am trying to minimize the number of blue vertices using the following operation: Choose a vertex $v_a$ in $A$ ...
2
votes
0answers
19 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$. ...
1
vote
1answer
35 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' ...
6
votes
2answers
120 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
107 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 ...
-1
votes
1answer
56 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
27 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
vote
2answers
80 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
34 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
52 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
52 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
122 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
63 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
63 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
97 views

LCA from children using bottom up approach?

I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom up without using depth. How would I go about traversing the tree, starting from any 2 ...
-1
votes
1answer
129 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
41 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 ...