Randomised enumeration of small witnesses using a decision oracle

Eugene L. Lawler, A procedure for computing the k k best solutions to discrete optimization problems and its application to the shortest path problem , Management Science 18

1972

Earlier work this paper cites.

C.P. Schnorr, Optimal algorithms for self-reducible problems , Proc. of the 3rd ICALP, Edinburgh University Press, 1976, pp. 322 – 337

1976

Earlier work this paper cites.

Samir Khuller and Vijay V. Vazirani, Planar graph coloring is not self-reducible, assuming P ≠ \neq NP , Theoretical Computer Science 88

1991

Earlier work this paper cites.

Noga Alon, Raphael Yuster, and Uri Zwick, Color-coding , Journal of the ACM 42

1995

Earlier work this paper cites.

M. Naor, L. J. Schulman and A. Srinivasan, Splitters and near-optimal derandomization , Proceedings of IEEE 36th Annual Foundations of Computer Science (FOCS 1995), Milwaukee, WI, 1995, pp. 182-191. doi: 10.1109/SFCS.1995.492475

1995

Earlier work this paper cites.

S. Staniford-Chen, S. Cheung, R. Crawford, M. Dilger, J. Frank, J. Hoagland, K. Levitt, C. Wee, R. Yip, and D. Zerkle, GrIDS - A graph based intrusion detection system for large networks , In Proc. of the 19th National Information Systems Security Conference, 1996, pp. 361–370

1996

Earlier work this paper cites.

B. Gelbord, Graphical techniques in intrusion detection systems , Information Networking, 2001. Proc. 15th International Conference on, 2001, pp. 253–258

2001

Earlier work this paper cites.

V. Arvind and Venkatesh Raman, Approximation algorithms for some parameterized counting problems , ISAAC 2002, LNCS, vol. 2518, Springer-Verlag Berlin Heidelberg, 2002, pp. 453–464

2002

Earlier work this paper cites.

Henning Fernau, On parameterized enumeration , Computing and Combinatorics (COCOON 2002), LNCS, vol. 2387, Springer Berlin Heidelberg, 2002, pp. 564–573

2002

Earlier work this paper cites.

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network motifs: Simple building blocks of complex networks , Science 298

2002

Cited alongside, same era.

J. Flum and M. Grohe, The parameterized complexity of counting problems , SIAM Journal on Computing 33

2004

Cited alongside, same era.

V. Sekar, Y. Xie, D.A. Maltz, M.K. Reiter, and H. Zhang, Toward a framework for internet forensic analysis , Third Workshop on Hot Topics in Networking (HotNets-III), 2004

2004

Cited alongside, same era.

J. Flum and M. Grohe, Parameterized complexity theory , Springer, 2006

2006

Cited alongside, same era.

N. Alon, P. Dao, I. Hajirasouliha, F. Hormozdiari, S. C. Sahinalp, Biomolecular network motif counting and discovery by color coding , Bioinformatics 24

2008

Cited alongside, same era.

Rodney G. Downey and Michael R. Fellows, Fundamentals of parameterized complexity , Springer London, 2013

2013

Later among the works it cites.

Andreas Björklund, Petteri Kaski, and 𝖫 \mathsf{L} ukasz Kowalik, Fast witness extraction using a decision oracle , Algorithms (ESA 2014), LNCS, vol. 8737, Springer Berlin Heidelberg, 2014, pp. 149–160

2014

Later among the works it cites.

Radu Curticapean and Dániel Marx, Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts , 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), 2014

2014

Later among the works it cites.

Andreas Björklund, Petteri Kaski, 𝖫 \mathsf{L} ukasz Kowalik, and Juho Lauri, Engineering motif search for large graphs , 2015 Proc. of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX 2015), SIAM, 2015, pp. 104–118

2015

Closest in time.