Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

learn more… | top users | synonyms

1
vote
3answers
99 views

Term for most degenerate tree with two children on every inner node

I'm looking for the name of a binary tree which is almost degenerate: at least one child of every interior node in the tree is a leaf. (Image from Penn State course STAT 557, Data Mining, lesson ...
2
votes
0answers
58 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping ...
3
votes
0answers
46 views

Heuristics to Find Circuits Allowing for Vertex Revists

I'm currently working on a project discussing applications of the Delaunay Triangulation, and the primary use-case is applications to TSP (or relaxations of the problem). See: ...
2
votes
0answers
21 views

Conjunctive Regular Path Queries and Subgraph Isomorphism

How do conjunctive regular path queries and subgraph isomorphism relate to each other? It seems that conjunctive regular path queries are a specialised form of subgraph isomorphism. The follow is ...
8
votes
1answer
63 views

About graphs whose edge set decomposes into perfect matchings

Is there a characterization of graphs whose edge set decomposes into a disjoint union of perfect matchings? One trivial class of such graphs are $d$-regular $(n,n)$-bipartite graphs. Their edge ...
3
votes
1answer
63 views

Simple algorithm for listing all 6-cycles in a directed graph

What's an easy-to-program way of listing all 6-cycles in a directed graph? I've done some reading on the general case of even cycles, but it's rather complicated. I found a really neat approach for ...
1
vote
0answers
28 views

Find all paths of length k [duplicate]

I have an adjacency matrix, call it A, representing a directed graph. I want to find all paths of length k. I know that A^k ...
1
vote
0answers
34 views

Sort graph nodes by density [closed]

Imagine villages (or Internet Routers) scattered all over the world (or World Wide Web) connected by roads or shipping lanes (or Cables). All villages (nodes) has the same amount of villagers which ...
4
votes
1answer
126 views

Longest simple walk in a complete graph

A simple walk is a path that does not contain the same edge twice. A simple walk can contain circuits and can be a circuit itself. It just shouldn't have the same edge twice. A simple undirected ...
2
votes
1answer
33 views

Are there other interpretations of |G| than |V|, that is |V(G)|?

This may be a basic question, but I'm hoping someone can settle this nagging doubt I'm having. I'm reading up on FPT complexity using a book by Downey and Fellows. It has some introductory examples ...
2
votes
1answer
39 views

Maximum bipartite matching when some nodes must be matched

Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched. ...
1
vote
1answer
45 views

What does pre-, post- and in-order walk mean for a n-ary tree?

The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and ...
2
votes
0answers
30 views

Complexity of cubic graph decomposition

I am aware that deciding the existence of decomposition of a cubic graph into edge disjoint claws is polynomial time solvable. What is the complexity of deciding the existence of decomposition of ...
0
votes
1answer
47 views

Finding common edges of two graphs [closed]

Is there any algorithm that finds the common edges and vertices between two graphs? Its not a common subgraph problem though, the edges which are common between the two graphs may not be connected to ...
2
votes
1answer
44 views

Proving algorithm for removing nodes from a complete graph with two kinds of edges

Lets say $G$ is complete undirected graph with a set of edges coloured either black or red. The problem is to find an algorithm answering if it is possible to remove a subset of nodes from $G$ in a ...
0
votes
2answers
46 views

Existence of shortest path in a graph with no negative cycles?

Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex. How do I prove that for every ...
4
votes
1answer
101 views

Unique path sums in a DAG using vertex instrumentation

I stumbled across this paper from Ball et al. In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control ...
1
vote
2answers
34 views

Finding a minimum set of dependencies in a cycle-filled dependency graph

I have a graph of a large number of targets. Each target depends on a list of other targets. The graph is very large and filled with cycles of dependencies. My goal is to find the smallest subset of ...
2
votes
1answer
74 views

Determine if items can be ordered grouping two simultaneous criteria

For a set of items with two properties, how can it be detemined if they can be ordered in a way so that for every value of either property all items of that value are grouped together. Obviously ...
2
votes
2answers
20 views

What are transitive successor and transitive predecessor in the graph?

I'm reading a book on compilers, Engineering a Compiler, 2nd ed. by Keith D. Cooper & Linda Torczon and I came a across two new terms that I can't understand, they are: transitive successor ...
2
votes
1answer
45 views

What is the graph with $8$ vertices and $12$ edges that has the most spanning trees? [closed]

I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?
3
votes
1answer
53 views

How to Prove NP-Completeness of Minimum Crossing Problem?

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. (from wikipedia) I know that the problem of counting the ...
1
vote
0answers
33 views

All paths of length n from a single graph vertex in a directed cyclic graph [duplicate]

Thanks in advance...looking for recommendations on an algorithm to find all paths of length n starting from a single node in a directed, cyclic graph. I am not concerned with at which node the path ...
2
votes
1answer
32 views

Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?

could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to ...
2
votes
1answer
50 views

Tolerated use of the term topology

In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees : 1) The first one: Node ...
0
votes
1answer
41 views

Graph theory, $n$ people sitting around table [closed]

$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice. How big can $k$ be in terms of $n$? Does everybody get to sit next to everybody ...
1
vote
1answer
12 views

How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant?

Given a random graph on $n$ vertices where each edge is included with probability $1/2$. Lets call it $G=(n,1/2)$. How can we show that the probability that this graph has a stable set of size at ...
4
votes
0answers
72 views

Computing the “at least k friends in common” graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
1
vote
1answer
58 views

SimRank on a weighted directed graph (how to calculate node similarity)

I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that ...
2
votes
1answer
104 views

Graph Families that are easy to color

What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter. Examples would be: Kneser graphs Chordal graphs Do ...
0
votes
2answers
130 views

scale-free networks and adjacency matrix

Given a distribution over graphs with $n$ nodes having the "scale-free" property, I would like to compute for a pair of vertices $(a,b)$ the probability that they are connected (or more precisely the ...
3
votes
1answer
62 views

Travelling Salesman which can repeat cities

In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This is ...
0
votes
1answer
15 views

Necessities for two undirected graphs being isomorphic

As far as I know, for two undirected graphs $G = (V, E) $ and $H = (V', E')$, the following criteria is necessary for them to be isomorphic: $|V| = |V'|$ $|E| = |E'|$ $G$ has $j$ nodes of degree $k$ ...
3
votes
1answer
83 views

Locally finite graph without an optimal path

If I have a locally finite graph (every node has finite number of neighbors) with positive edge weights, is it possible for there to be a path between some start node and goal node but no shortest ...
3
votes
0answers
38 views

Finding partial traveling salesman path of specified length

For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial ...
-2
votes
2answers
77 views

Undirected graph G that has 12 vertices, 66 edges and 3 connected components?

Why would it be impossible to draw an undirected graph G that has 12 vertices, with 3 connected components if G had 66 edges?
-1
votes
2answers
79 views

Why is T not a minimum spanning tree of G?

The Problem: Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.    a. True of ...
1
vote
1answer
58 views

How to draw a graph to disprove this statement?

The Problem: Indicate whether the following statements are true or false: a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum ...
0
votes
1answer
28 views

Algorithm deciding if a radius of a graph is two

Given an unweighted, undirected graph, what is the time complexity to decide if its radius is at most 2? Are there any faster algorithms than doing BFS on each node?
2
votes
1answer
86 views

Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$. Now we decrease the weight by $k$ ...
3
votes
2answers
53 views

What is the appropriate algorithm for bipartite matching with constraints?

I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it). Let's say we have a lot of employees and a few jobs to be done. Each ...
2
votes
1answer
49 views

Strongly connected components on a DAG

What is supposed to be the right result of an SCC algorithm running on a DAG. should it return "no components" or "there are V components of size 1"? I suspect it will return the latter (since it ...
2
votes
1answer
38 views

Dominator Tree for DAG

Is there a fast algorithm to compute dominator tree for acyclic graphs? The Lengauer-Tarjan Algorithm is a fast algorithm for general flowgraphs. But if a graph is acyclic, do we have a faster ...
-1
votes
1answer
19 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 ...
3
votes
1answer
183 views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
1
vote
1answer
61 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
28 views

Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of ...
1
vote
1answer
84 views

How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs? [closed]

As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable? This is not a "technical" ...
3
votes
1answer
64 views

Is the minimal number of colors needed to color a graph some fixed number?

Consider to following decision problem: Input: Undirected graph $G=(V,E)$ Question: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices ...
1
vote
1answer
33 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 ...