The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
2answers
56 views

Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...
7
votes
1answer
251 views

A matching that covers vertices with maximum degree

We have a graph G with maximum degree $\Delta$. The induced subgraph on vertices with degree equal to $\Delta$ is a bipartite graph (while the original graph is not). Prove that G has a matching that ...
1
vote
1answer
147 views

Subgraph isomorphism problem on 2d triangular lattices.

Is there an efficient (possibly probabilistic/approximate) algorithm for determining whether a particular graph is the subgraph of an infinite two dimensional triangular lattice? How about three ...
1
vote
1answer
455 views

Minimum spanning subgraph with at least one incoming and one outgoing edge

Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which ...
1
vote
1answer
320 views

almost-bipartite nearly-isolated subgraphs

I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is bipartite-plus-a-few-edges ...