4 papers
Node-Weighted Triangles: Faster and Simpler
Shyan Akmal, Nick Fischer
Weighted variants of triangle detection are an important object of study because of their prominence in fine-grained complexity. We revisit the Node-Weighted Triangle problem, wher…
Graph Coloring Below Guarantees via Co-Triangle Packing
Shyan Akmal, Tomohiro Koana
In the -Coloring Problem, we are given a graph on nodes, and tasked with determining if its vertices can be properly colored using colors. In this paper we study b…
Faster Edge Coloring by Partition Sieving
Shyan Akmal, Tomohiro Koana
In the Edge Coloring problem, we are given an undirected graph with vertices and edges, and are tasked with finding the smallest positive integer so that the edges…
An Enumerative Perspective on Connectivity
Shyan Akmal
Connectivity (or equivalently, unweighted maximum flow) is an important measure in graph theory and combinatorial optimization. Given a graph with vertices and , the con…