Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

4,341 questions
Filter by
Sorted by
Tagged with
870 views

Reconstructing Graphs from Degree Distribution

Given a degree distribution, how fast can we construct a graph that follows the given degree distribution? A link or algorithm sketch would be good. The algorithm should report a "no" incase no graph ...
200 views

Optimizing order of graph reduction to minimize memory usage

Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used. That is, given ...
43k views

Dijsktra's algorithm applied to travelling salesman problem

I am a novice(total newbie to computational complexity theory) and I have a question. Lets say we have 'Traveling Salesman Problem' ,will the following application of Dijkstra's Algorithms solve it? ...
4k views

Find the minimal number of runs to visit every edge of a directed graph

I am looking for an algorithm to find a minimal traversal of a directed graph of the following type. Two vertices are given, a start vertex and a terminating vertex. The traversal consists of several ...
509 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
5k views

Finding the maximum bandwidth along a single path in a network

I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link bandwidths....
863 views

Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED

NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really ...
1k views

How to approach Dynamic graph related problems

I asked this question at generic stackoverflow and I was directed here. It will be great if some one can explain how to approach partial or fully dynamic graph problems in general. For example: ...
232 views

Simple paths with halt in between in directed graphs

I have two problems related to paths in a directed graph. Let $G=(V,E)$ be a directed graph with source $s \in V$ and target $t \in V$. Let $v \in V \setminus \{s,t\}$ be another vertex in $G$. Find ...
2k views

Is Logical Min-Cut NP-Complete?

Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
18k views

Find the longest path from root to leaf in a tree

I have a tree (in the graph theory sense), such as the following example: This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length ...
258 views

Modified Djikstra's algorithm

So, I'm trying to conceptualize something: Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats: movements on ...
20k views

Shortest Path on an Undirected Graph?

So I thought this (though somewhat basic) question belonged here: Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...
160 views

Find minimum number 1's so the matrix consist of 1 connected region of 1's

Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ ...
4k views

NP-completeness of a spanning tree problem

I was reviewing some NP-complete problems on this site, and I meet one interesting problem from NP completeness proof of a spanning tree problem In this problem, I am interested in the original ...
4k views

Chinese Postman Problem: finding best connections between odd-degree nodes

I am writing a Program, solving the Chinese Postman Problem (also known as route inspection problem) in an undirected draph and currently facing the problem to find the best additional edges to ...
6k views

Where to get graphs to test my search algorithms against?

I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc. At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'...
4k views

How to construct the found path in bidirectional search

I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables (...
1k views

How many shortest distances change when adding an edge to a graph?

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
7k views

How to implement AO* algorithm?

I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-...
961 views

Optimal algorithm for finding the girth of a sparse graph?

I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity. I thought about some modification on Tarjan's algorithm for ...
4k views

Does spanning tree make sense for DAG?

Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.
1k views

Proving that directed graph diagnosis is NP-hard

I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and ...
6k views

NP completeness proof of a spanning tree problem

I am looking for some hints in a question asked by my instructor. So I just figured out this decision problem is $\sf{NP\text{-}complete}$: In a graph $G$, is there a spanning tree in $G$ that ...
7k views

Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction? For people who were following in the ...
568 views

Is Directed Graph a Graph?

I came across an issue with the definition of a (directed) graph in Sipser's Introduction to the theory of computation, 2nd Ed. On pp.10, An undirected graph, or simply a graph, is a set of points ...
455 views

How many edges can a unipathic graph have?

A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex. Unipathic graphs can have cycles. For example, a doubly linked list (not a ...
1k views

Find shortest paths in a weighed unipathic graph

A directed graph is said to be unipathic if for any two vertices $u$ and $v$ in the graph $G=(V,E)$, there is at most one simple path from $u$ to $v$. Suppose I am given a unipathic graph $G$ such ...
746 views

Improve worst case time of depth first search on Euler graphs

How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point? I need to do the whole search but it is not fast enough for ...
2k views

How Do Common Pathfinding Algorithms Compare To Human Process

This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different ...
109 views

An indexing function for graphs

Definition from wikipedia: A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of nodes together with a set $E$ of edges, which are two-element subsets of $V$. The set of all finite ...
12k views

How hard is counting the number of simple paths between two nodes in a directed graph?

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search). However it seems that, ...
2k views