Questions tagged [graphs]

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

4,666 questions
Filter by
Sorted by
Tagged with
3k views

• 153
733 views

NP-completeness of graph isomorphism through edge contractions with an edge validity condition

Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
248 views

• 13
191 views

Proof of NP-completeness of graph isomorphism through edge contractions that reduce a metric [duplicate]

Duplicate: NP-completeness of graph isomorphism through edge contractions with an edge validity condition I know that graph contractability is $NP$-complete. To be specific given $G=(V_1,E_1)$ ...
335 views

Algorithm to test a graph for $t$-transitivity

I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive. I am also interested in knowing if this problem is in P, NP, NPC or some other ...
• 651
6k views

Getting parallel items in dependency resolution

I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
• 273
430 views

Is there a formal name for this graph operation?

I'm writing a small function to alter a graph in a certain way and was wondering if there is a formal name for the operation. The operation takes two distinct edges, injects a new node between the ...
• 171
Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$. I would like to know if there are already algorithms for calculating the following decision problem: Are there at least two ...