[1]
R. Sharan, Graph modification problems and their applications to genomic research, PhD degree dissertation, Tel-Aviv University, 2002.
[2]
S. L. Lauritzen and D. J. Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems, Readings in Uncertain Reasing, pp. 415-448, 1990.
[3]
F. Mancini, Graph modification problems related to graph classes, PhD degree dissertation, University of Bergen Norway, 2008.
[4]
R. Downey and M. Fellows, Parameterized Complexity. New York: Springer, 1999.
[5]
J. Chen, Parameterized computation and complexity: A new approach dealing with NP-Hardness, Journal of Computer Science and Technology, vol. 20, no. 1, pp. 18-37, 2005.
[6]
J. Chen, I. A. Kanj, and W. Jia, Vertex cover: Further observations and further improvements, Journal of Algorithms, vol. 41, pp. 280-301, 2001.
[7]
S. Thomassé, A 4k2 kernel for feedback vertex set, ACM Transactions on Algorithms, vol. 6, no. 2, pp. 1-6, 2010.
[8]
J. Guo, A more effective linear kernelization for cluster editing, Theoretical Computer Science, vol. 410, pp. 718-726, 2009.
[9]
S. Kratsch and M. Wahlström, Two edge modification problems without polynomial kernels, Discrete Optimization, vol. 10, no. 3, pp. 193-199, 2013.
[10]
L. Cai and Y. Cai, Incompressibility of H-free edge modification problems, in Proc. 8th International Symposium on Parameterized and Exact Computation (IPEC), Lecture Notes in Computer Science Volume 8246, Sophia Antipolis, France, 2013, pp. 84-96.
[11]
H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems without polynomial kernels, Journal of Computer and System Sciences, vol. 75, no. 8, pp. 423-434, 2009.
[12]
A. Rai, Kernel lower bounds: A survey, A thesis submitted to the board of studies in Theoretical Computer Science, 2012.
[13]
F. N. Abu-Khzam, Kernelization algorithms for d-hitting set problems, in Proc. 10th International Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 4619, Halifax, Canada, 2007, pp. 434-445.
[14]
F. V. Fomin, S. Saurabh, and Y. Villanger, A polynomial kernel for proper interval deletion, SIAM J. Discrete Math., vol. 27, no. 4, pp. 1964-1976, 2013.
[15]
J. Dĺaz and D. M. Thilikos, Fast FPT-Algorithms for cleaning grids, in Proc. 23rd Annual Conference on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science Volume 3884, Marseille, 2006, pp. 361-371.
[16]
H. Moser, D. M. Thilikos, Parameterized complexity of finding regular induced subgraphs, Journal of Discrete Algorithms, vol. 7, pp. 181-190, 2009.
[17]
E. Ghosh, S. Kolay, M. Kumar, P. Misra, F. Panolan, A. Rai, and M. S. Ramanujan, Faster parameterized algorithms for deletion to split graphs, in Proc. 13th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science Volume 7357, Helsinki, Finland, 2012, pp. 107-118.
[18]
J. Guo, C. Komusiewicz, R. Niedermeier, and J. Uhlmann, A more relaxed model for graph-based data cluster: s-plex editing, SIAM J. Discrete Math., vol. 24, no. 4, pp. 1662-1683, 2010.
[19]
R. V. Bevern, H. Moser, and R. Niedermeier, Kernelization through tidying: A case study based on s-plex cluster vertex deletion, in Proc. 9th Latin American Theoretical Infornatics Symposium (LATIN), Lecture Notes in Computer Science 6034, México, 2010, pp. 528-539.
[20]
J. Flum and M. Grohe, Parameterized complexity theory, Texts in Theoretical Computer Scicence, An EATCS Series. Springer, 2006.
[21]
P. Erdös and R. Rado, Intersection theorems for systems of sets, Journal of London Mathematical Society, vol. 35, pp. 85-90, 1960.
[22]
S. Kratsch, Polynomial kernelization for MIN F+Π1 and MAX NP, Algorithmica, vol. 63, nos. 1-2, pp. 532-550, 2012.
[23]
F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier, Fixed-parameter algorithms for cluster vertex deletion, Theory of Computing Systems, vol. 47, no. 1, pp. 196-217, 2010.
[24]
C. Paul, A. Perez, and S. Thomassé, Conflict packing yields linear vertex-kernels for k-FAST, k-dense RTI and a related problem, in Proc. 36th Conference on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science Volume 6907, Warsaw, Poland, 2011, pp. 497-507.
[25]
A. Perez, Kernelization algorithms for graph and other structure modification problems, Extented Abstract of PhD Thesis, 2012.
[27]
J. Chen, Y. Liu, S. Lu, B. O’Sullivan, and I. Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, Journal of The ACM, vol. 55, no. 5, pp. 1-19, 2008.
[28]
A. Rafiey, Single exponential FPT algorithm for interval vertex deletion and interval completion problem, CoRR, abs/1211.4629, 2012.
[29]
Y. Cao and D. Marx, Interval deletion is fixed-parameter tractable, in Proc. 25rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Portland, Oregon, 2014, pp.122-141.
[30]
S. Kratsch and M. Wahlström, Compression via matroids: A randomized polynomial kernel for odd cycle transversal, in Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, Japan, 2012, pp.94-103.
[31]
J. Guo and R. Niedermeier, Linear problem kernels for NP-hard problems on planar graphs, in Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science Volume 4596, Wroclaw, Poland, 2007, pp. 375-386.
[32]
J. Wang, Y. Yang, J. Guo, and J. Chen, Planar graph vertex partition for linear problem kernels, Journal of Computer and System Sciences, vol. 79, no. 5, pp. 609-621, 2013.
[33]
J. Wang, W. Luo, Q. Feng, J. Guo, and J. Chen, Improved linear problem kernel for planar connected dominating set, Theoretical Computer Science, vol. 511, pp. 2-12, 2013.
[34]
H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos, (Meta) Kernelization, in Proc. 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Atlanta, Georgia, 2009, pp. 629-638.
[35]
Q. Feng, J. Wang, and J. Chen, Matching and weighted P2-packing: Algorithms and kernels, Theoretical Computer Science, vol. 522, pp. 85-94, 2014.
[36]
J. Wang, P. Tan, J. Yao, Q. Feng, and J. Chen, On the minimum link-length rectilinear spanning path problem: Complexity and Algorithms, IEEE Transactions on Computers, , 2014.
[37]
Q. Feng, J. Wang, S. Li, and J. Chen, Randomized parameterized algorithms for P2-packing and co-path packing problems, Journal of Combinatorial Optimization, 2014, .
[38]
J. Chen and J. Meng, A 2k kernel for the cluster editing problem, Journal of Computer and System Sciences, vol. 78, no.1, pp. 211-220, 2012.
[39]
J. Guo, F. Hüffner, C. Komusiewicz, and Y. Zhang, Improved algorithms for bicluster editing, in Proc. 5th Theory and Applications of Models of Computation (TAMC), Lecture Notes in Computer Science Volume 4978, Xi’an, China, 2008, pp. 445-456.
[40]
C. Komusiewicz and J. Uhlmann, A cubic-vertex kernel for flip consensus tree, Algorithmica, vol. 68, no. 1, pp. 81-108, 2014.
[41]
S. Guillemot, C. Paul, and A. Perez, On the (non-)existence of polynomial kernels for Pl-free edge modification problems, Algorithmica, vol. 65, no. 4, pp. 900-926, 2013.
[42]
S. Bessy, C. Paul, and A. Perez, Polynomial kernels for 3-leaf power graph modification problems, Discrete Applied Mathmatics, vol. 158, pp. 1732-1744, 2010.
[43]
Y. Cao and J. Chen, Cluster editing: Kernelization based on edge cuts, Algorithmica, vol. 64, pp. 152-169, 2012.
[44]
J. Nastos and Y. Gao, Familial groups in social networks, Social Networks, vol. 35, no. 3, pp. 439-450, 2013.
[45]
Y. Cao and D. Marx, Chordal editing is fixed-parameter tractable, in Proc. 31st International Symposium on Theoretical Aspects of Computer Science (STACS), Lyon, France, 2014, pp. 214-225.
[46]
D. Brügmann, C. Komusiewicz, and H. Moser, On generating triangle-free graphs, Electronic Notes in Discrete Mathematics, vol. 32, pp. 51-58, 2009.
[47]
G. Xia and Y. Zhang, Kernelization for cycle transversal problems, Discrete Applied Mathmatics, vol. 160, nos. 7-8, pp. 1224-1231, 2012.
[48]
J. Guo, Problem kernels for NP-Complete edge deletion problems: split and related graphs, in Proc. 18th International Symposium on Algorithms and Computation, (ISAAC), Lecture Notes in Computer Science Volume 4835, Sendai, Japan, 2007, pp. 915-926.
[49]
P. G. Drange, F. V. Fomin, M. Pilipczuk, and Y. Villanger, Exploring subexponential parameterized complexity of completion problems, in Proc. 31st International Symposium on Theoretical Aspects of Computer Science (STACS), Lyon, France, 2014, pp. 288-299.
[50]
H. Kaplan, R. Shamir, and R. E. Tarjan, Tractability of parameterized completion problems on chordal, strongly chordal, and proper intervalgraphs, SIAM J. Comput., vol. 28, no. 5, pp. 1906-1922, 1999.
[51]
S. Bessy and A. Perez, Polynomial kernels for proper interval completion and related problems, Information and Computation, vol. 231, pp. 89-108, 2013.
[52]
A. Natanzon, R. Shamir, and R. Sharan, A polynomial approximation algorithm for the minimum fill-in problem, SIAM J. Comput., vol. 30, no. 4, pp. 1067-1079, 2000.
[53]
P. J. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Computer and Mathematics with Applications, vol. 25, no. 7, pp. 15-25, 1993.
[54]
F. V. Fomin and Y. Villanger, Subexponential parameterized algorithm for minimum fill-in, in Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, Japan, 2012, pp. 1737-1746.
[55]
Y. Villanger, P. Heggernes, C. Paul, and J. A. Telle, Interval completion is fixed-parameter tractable, SIAM Journal on Computing, vol. 38, no. 5, pp. 2007-2020, 2009.
