Exact Weight 3-Star Detection

Given an nn node graph G=(V,E)G = (V, E) with edge weights w:EWw: E \rightarrow W and a target value tt, determine whether there is a (not necessarily induced) 33-star (i.e. 44 nodes with 33 edges connecting a central node to the other 33 nodes) whose edge weights sum to tt.

Parameters

  • nn: number of nodes
  • mm: number of edges
  • tt: target value

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 4 of 4 reductions

Other relevant algorithms

Insuffient Data to display table