Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication

DOI10.1137/070695149MaRDI QIDQ3558009zbMATH OpenOpenAlexFDO

Authors Artur Czumaj, Andrzej Lingas

Publication date 29 April 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/17465/1/WRAP_Czumaj_GetPDFServlet2.pdf

zbMATH Keywords

graph algorithmsgraph trianglematrix multiplicationtime complexityvertex-weighted graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding a heaviest triangle is not harder than matrix multiplication
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Finding the largest triangle in a graph in expected quadratic time

Cited in

(18)

• Extreme witnesses and their applications
• Finding the largest triangle in a graph in expected quadratic time
• Fooling views: a new lower bound technique for distributed computations under congestion
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Finding a heaviest triangle is not harder than matrix multiplication
• BetweenO(nm) andO(n^alpha)
• Extreme witnesses and their applications
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Even faster elastic-degenerate string matching via fast matrix multiplication
• On minimum witnesses for Boolean matrix multiplication
• Detecting and counting small pattern graphs
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Deterministic 3SUM-hardness
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds

This page was built for publication: Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558009)