Akash Kumar

activity

20182021

collaborators

Showing cs.DMShow all

2 papers · 1 filter

cs.DM2019

Random walks and forbidden minors II: A $poly (d ε^{- 1})$ -query tester for minor-closed properties of bounded-degree graphs

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be a graph with $n$ vertices and maximum degree $d$ . Fix some minor-closed property $P$ (such as planarity). We say that $G$ is $ε$ -far from $\mathcal{P…

cs.DM2018

Finding forbidden minors in sublinear time: a $n^{1/2 + o (1)}$ -query one-sided tester for minor closed properties on bounded degree graphs

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$ , and suppose one must remove $ε n$ edges from $G$ to make it $H$ -minor free (for…

Random walks and forbidden minors II: A poly(dε−1)-query tester for minor-closed properties of bounded-degree graphs

Finding forbidden minors in sublinear time: a n1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs

Random walks and forbidden minors II: A $poly (d ε^{- 1})$ -query tester for minor-closed properties of bounded-degree graphs

Finding forbidden minors in sublinear time: a $n^{1/2 + o (1)}$ -query one-sided tester for minor closed properties on bounded degree graphs