Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

Filter by
Sorted by
Tagged with
-3
votes
1answer
1k views

is Facebook friendship graph connected? [closed]

In Facebook friendship graph the nodes are profiles and the edges are friendships (alternatively subscriptions could serve as well if we allow directed edges). Is the graph connected? (Obviously it ...
-3
votes
1answer
113 views

Finding the maximum no. of people who get along in a group [closed]

Suppose that there are 15 people in a room. Assume that each person gets along with other people in the room (but not everyone). (Note that the "feeling is mutual" between any two people who are ...
-3
votes
1answer
89 views

tagging and graph “compression”

I have a question on stack-overflow about "compressing" a graph. Suppose I have tags from a finite set $T$ and objects from a finite set $O$. Moreover there are (uni-directional) links from elements ...
-3
votes
1answer
518 views

How to find the minimum number of vertices to join disconnected components of a graph? [closed]

Suppose, i have a graph with fixed number of nodes and edges. However, all the nodes doesn't remain active all the time causing the graph disconnected. In this sort of situation, i want to find out ...
-3
votes
0answers
28 views

Algorithm to decide percentage of data from previous node, current node and forward nodes

I have a graph-like structure, let's say there is one node $C$, who has 2 predecessors $A,B$ and 1 successor $D$. I have a value of $C$. Let's say value at $C=30$%. From this, I could infer that I ...
-3
votes
1answer
7k views

Efficient algorithm to create a directed dependency graph

I am looking for an efficient algorithm to create a graph like this: Initially the graph is filled with x then hs then ...
-4
votes
1answer
3k views

Algorithm to find shortest path from a set of nodes to another set of nodes? [closed]

I'm developing a route planner, and I was reading some graph theory. I read a little bit of Dijkstra's shortest path, shooting star and turn restrictions, and I tend to think that this algorithms are ...
-4
votes
1answer
413 views

“tree-like” vs “DAG-like” resolution

hi all there seems to be a deep/not-much-explored phenomenon in the way that SAT resolution proofs can define a tree and/or a DAG & its relationship to lower bounds/circuit complexity. could there ...
-4
votes
1answer
104 views

conversion to DAG

Can we reverse directions instead?
-4
votes
1answer
886 views

Compact representation of DAG,

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that: ...
-4
votes
1answer
147 views

Is a k-connected graph also k-1 connected?

So I'm reading about k-connected graphs, and I'm a little confused about them. This is the main definition I've seen: A graph is k connected if and only if for any distinct x, y vertices in the graph,...
-4
votes
1answer
275 views

How to prove that a 3-connected 5-regular planar graph has chromatic number <= 4? [closed]

I can think of a way that to prove a 3-connected 5-regular planar graph does not contain a 5-critical subgraph. We can choose two non-adjacent vertices a,b and contract them into a single vertex. If ...
-4
votes
1answer
181 views

Destroy shortest path in graph

Given graph G(V,E)and two vertices A and B, show how to eliminate the least number of edges so that length of shortest path between A and B become longer.(I need an algorithm)
-4
votes
1answer
66 views

How to find the pair of two of edges which, removed from a graph, makes it disconnected?

How to find ALL the pair of two edges which, removed from a graph, makes it disconnected? I was thinking about a O(M * (N + M )) algorithm, and I am wondering if there is a better algorithm. Thanks in ...
-4
votes
2answers
265 views

Polynomial algorithm for HAMPATH transformed into an algorithm that solves the problem sequentially? [closed]

Let us assume (probably wrongly) that P=NP, meaning that we know a way to output a hampath if it exists. A graph has $n$ vertexes. Can the algorithm that solves the problem be modified in ...
-4
votes
0answers
77 views

Argument that Graph Isomorphism is polynomial via reduction to CNF

In short we found 3 invertible transformations which imply that Graph Isomorphism is polynomial. Meta reasoning: Isomorphism preserving transformation CNF to "sparse" CNF is possible and ...
-4
votes
1answer
52 views

Distinguish Graph from Tree using Adjacency Matrix

Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle). For example, given the adjacency matrix: ...
-4
votes
2answers
117 views

Looking for an algorithm to construct a graph from two subgraphs

I am looking for an algorithm to construct a graph from two subgraphs. The problem is as following: Given two graphs g1(V, E) and g2(V, E), find a graph G(V, E) where V(g1) ⊆ V(G), V(g2) ⊆ V(G), E(g1)...
-4
votes
1answer
1k views

Time complexity of finding the shortest path in DAG [closed]

I apologize for seemingly basic question: I saw numerous times that the time complexity of finding the shortest path in directed acyclic graph is O(|V| + |E|). ...
-5
votes
1answer
807 views

What is the complexity of the fastest method of k-coloring any graph? [closed]

I heard brute-force is the only method. Is there any other way? Is there a way to prove that the complexity cannot be exponential?
-5
votes
2answers
3k views

Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
-5
votes
1answer
722 views

Self-avoiding walk in Graph [closed]

Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$? Long question: Edit: This question is not about p = np. I am searching for a way to calculate the numbers ...
-5
votes
1answer
281 views

Does any DAG can be topologically sorted? [closed]

I am not good enough in computer science. My intention is to solve some programming problem in terms of DAG's. The key point is that before getting them into database, I need run "topological sort" in ...

1
23 24 25 26
27