[1] |
Agrawal, Akanksha, Kolay, Sudeshna, Lokshtanov, Daniel, and Saurabh, Saket. 2016. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In LATIN 2016: Theoretical Informatics. Lecture Notes in Computer Science, Vol. 9644. Springer, 1-13. · Zbl 1417.68145 |
[2] |
Agrawal, Akanksha, Lokshtanov, Daniel, Misra, Pranabendu, Saurabh, Saket, and Zehavi, Meirav. 2017. Feedback vertex set inspired kernel for chordal vertex deletion. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17). SIAM, 1383-1398. · Zbl 1410.68270 |
[3] |
Agrawal, Akanksha, Lokshtanov, Daniel, Misra, Pranabendu, Saurabh, Saket, and Zehavi, Meirav. 2019. Feedback vertex set inspired kernel for chordal vertex deletion. ACM Transactions on Algorithms15, 1 (2019), Article 11, 28 pages. · Zbl 1454.68088 |
[4] |
Agrawal, Akanksha, Lokshtanov, Daniel, Mouawad, Amer E., and Saurabh, Saket. 2018. Simultaneous feedback vertex set: A parameterized perspective. ACM Transactions on Computation Theory10, 4 (2018), Article 18, 25 pages. · Zbl 1485.68169 |
[5] |
Bar-Noy, Amotz, Bar-Yehuda, Reuven, Freund, Ari, Naor, Joseph, and Schieber, Baruch. 2001. A unified approach to approximating resource allocation and scheduling. Journal of the ACM48, 5 (2001), 1069-1090. · Zbl 1323.68564 |
[6] |
Bodlaender, Hans L., Downey, Rodney G., Fellows, Michael R., and Hermelin, Danny. 2009. On problems without polynomial kernels. Journal of Computer and System Sciences75, 8 (2009), 423-434. · Zbl 1192.68288 |
[7] |
Bollobás, Béla. 1965. On generalized graphs. Acta Mathematica Hungarica16, 3-4 (1965), 447-452. · Zbl 0138.19404 |
[8] |
Brandstädt, Andreas, Le, Van Bang, and Spinrad, Jeremy P.. 1999. Graph Classes: A Survey. SIAM, Philadelphia, PA. · Zbl 0919.05001 |
[9] |
Cao, Yixin. 2016. Linear recognition of almost interval graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). SIAM, 1096-1115. · Zbl 1410.68284 |
[10] |
Cao, Yixin. 2017. Unit interval editing is fixed-parameter tractable. Information and Computation253 (2017), 109-126. · Zbl 1359.68230 |
[11] |
Cao, Yixin and Marx, Dániel. 2015. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms11, 3 (2015), Article 21, 35 pages. · Zbl 1398.68220 |
[12] |
Cao, Yixin and Marx, Dániel. 2016. Chordal editing is fixed-parameter tractable. Algorithmica75, 1 (2016), 118-137. · Zbl 1344.68095 |
[13] |
Cygan, Marek, Fomin, Fedor V., Kowalik, Łukasz, Lokshtanov, Daniel, Marx, Daniel, Pilipczuk, Marcin, Pilipczuk, Michal, and Saurabh, Saket. 2015. Parameterized Algorithms. Springer-Verlag, Cham, Switzerland. · Zbl 1334.90001 |
[14] |
Cygan, Marek, Kowalik, Łukasz, and Pilipczuk, Marcin. 2013. Open problems from Workshop on Kernels. |
[15] |
Dell, Holger and Marx, Dániel. 2012. Kernelization of packing problems. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 68-81. · Zbl 1421.68072 |
[16] |
Dell, Holger and Melkebeek, Dieter van. 2014. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM61, 4 (2014), Article 23, 27 pages. · Zbl 1321.68274 |
[17] |
Diestel, Reinhard. 2010. Graph Theory (4th ed.). Springer-Verlag, Heidelberg, Germany. · Zbl 1204.05001 |
[18] |
Downey, Rodney G. and Fellows, Michael R.. 2013. Fundamentals of Parameterized Complexity. Springer, London. · Zbl 1358.68006 |
[19] |
Drucker, Andrew. 2015. New limits to classical and quantum instance compression. SIAM Journal on Computing44, 5 (2015), 1443-1479. · Zbl 1330.68092 |
[20] |
Flum, Jörg and Grohe, Martin. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin, Germany. · Zbl 1143.68016 |
[21] |
Fomin, Fedor V., Jansen, Bart M. P., and Pilipczuk, Michal. 2014. Preprocessing subgraph and minor problems: When does a small vertex cover help?Journal of Computer and System Sciences80, 2 (2014), 468-495. · Zbl 1277.68095 |
[22] |
Fomin, Fedor V., Lokshtanov, Daniel, Misra, Neeldhara, and Saurabh, Saket. 2012. Planar f-deletion: Approximation, kernelization and optimal FPT algorithms. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12). IEEE, Los Alamitos, CA, 470-479. |
[23] |
Fomin, Fedor V., Lokshtanov, Daniel, Panolan, Fahad, and Saurabh, Saket. 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM63, 4 (2016), Article 29, 60 pages. · Zbl 1410.05212 |
[24] |
Fomin, Fedor V. and Saurabh, Saket. 2014. Kernelization methods for fixed-parameter tractability. In Tractability: Practical Approaches to Hard Problems, L. Bordeaux, Y. Hamadi, and P. Kohli (Eds.). Cambridge University Press, Cambridge, UK, 260-282. |
[25] |
Fortnow, Lance and Santhanam, Rahul. 2011. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences77, 1 (2011), 91-106. · Zbl 1233.68144 |
[26] |
Fujito, Toshihiro. 1998. A unified approximation algorithm for node-deletion problems. Discrete Applied Mathematics86, 2-3 (1998), 213-231. · Zbl 0906.68106 |
[27] |
Fulkerson, Delbert and Gross, Oliver. 1965. Incidence matrices and interval graphs. Pacific Journal of Mathematics15, 3 (1965), 835-855. · Zbl 0132.21001 |
[28] |
Golumbic, Martin Charles. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY. · Zbl 0541.05054 |
[29] |
Guo, Jiong and Niedermeier, Rolf. 2007. Invitation to data reduction and problem kernelization. ACM SIGACT News38, 1 (2007), 31-45. |
[30] |
Hermelin, Danny, Kratsch, Stefan, Soltys, Karolina, Wahlström, Magnus, and Wu, Xi. 2015. A completeness theory for polynomial (turing) kernelization. Algorithmica71, 3 (2015), 702-730. · Zbl 1312.68102 |
[31] |
Hermelin, Danny and Wu, Xi. 2012. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 104-113. · Zbl 1421.68086 |
[32] |
Jansen, Bart M. P.. 2013. The Power of Data Reduction: Kernels for Fundamental Graph Problems. . Utrecht University. |
[33] |
Jansen, Bart M. P., Lokshtanov, Daniel, and Saurabh, Saket. 2014. A near-optimal planarization algorithm. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). SIAM, 1802-1811. · Zbl 1423.68341 |
[34] |
Jansen, Bart M. P. and Pilipczuk, Marcin. 2017. Approximation and kernelization for chordal vertex deletion. In Proceedings of the T28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17). SIAM, 1399-1418. · Zbl 1410.68300 |
[35] |
Jansen, Bart M. P. and Pilipczuk, Marcin. 2017. Approximation and kernelization for chordal vertex deletion. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17. SIAM, 1399-1418. · Zbl 1410.68300 |
[36] |
Jansen, Bart M. P. and Pilipczuk, Marcin. 2018. Approximation and kernelization for chordal vertex deletion. SIAM Journal on Discrete Mathematics32, 3 (2018), 2258-2301. · Zbl 1394.05124 |
[37] |
Ke, Yuping, Cao, Yixin, Ouyang, Xiating, Li, Wenjun, and Wang, Jianxin. 2018. Unit interval vertex deletion: Fewer vertices are relevant. Journal of Computer and System Sciences95 (2018), 109-121. · Zbl 1391.68058 |
[38] |
Kendall, David. 1969. Incidence matrices, interval graphs and seriation in archeology. Pacific Journal of Mathematics28, 3 (1969), 565-570. · Zbl 0185.03301 |
[39] |
Kim, Eun Jung and Kwon, O-Joung. 2017. A polynomial kernel for block graph deletion. Algorithmica79, 1 (2017), 251-270. · Zbl 1372.68134 |
[40] |
Kim, Eun Jung, Langer, Alexander, Paul, Christophe, Reidl, Felix, Rossmanith, Peter, Sau, Ignasi, and Sikdar, Somnath. 2016. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms12, 2 (2016), Article 21, 41 pages. · Zbl 1398.68245 |
[41] |
Kratsch, Stefan. 2014. Recent developments in kernelization: A survey. · Zbl 1409.68144 |
[42] |
Kratsch, Stefan and Wahlström, Magnus. 2012. Representative sets and irrelevant vertices: New tools for kernelization. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12). IEEE, Los Alamitos, CA, 450-459. |
[43] |
Lay, David C.. 2006. Linear Algebra and Its Applications. Pearson/Addison-Wesley. |
[44] |
Lekkeikerker, C. and Boland, J.. 1962. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae51, 1 (1962), 45-64. · Zbl 0105.17501 |
[45] |
Lewis, John M. and Yannakakis, Mihalis. 1980. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences20, 2 (1980), 219-230. · Zbl 0436.68029 |
[46] |
Lokshtanov, Daniel, Misra, Neeldhara, and Saurabh, Saket. 2012. Kernelization—Preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Springer, Heidelberg, Germany, 129-161. · Zbl 1358.68141 |
[47] |
Lovász, László. 1972. A characterization of perfect graphs. Journal of Combinatorial Theory, Series B13, 2 (1972), 95-98. · Zbl 0241.05107 |
[48] |
Lund, Carsten and Yannakakis, Mihalis. 1994. On the hardness of approximating minimization problems. Journal of the ACM41, 5 (1994), 960-981. · Zbl 0814.68064 |
[49] |
Marx, Dániel. 2009. A parameterized view on matroid optimization problems. Theoretical Computer Science410, 44 (2009), 4471-4479. · Zbl 1180.90275 |
[50] |
Marx, Dániel. 2010. Chordal deletion is fixed-parameter tractable. Algorithmica57, 4 (2010), 747-768. · Zbl 1220.05066 |
[51] |
Niedermeier, Rolf. 2006. Invitation to Fixed-Parameter Algorithms. Vol. 31. Oxford University Press, Oxford, UK. · Zbl 1095.68038 |
[52] |
Oxley, James G.. 2006. Matroid Theory. Vol. 3. Oxford University Press, New York, NY. · Zbl 1115.05001 |
[53] |
Yannakakis, Mihalis. 1978. Node- and edge-deletion NP-complete problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC’78). ACM, New York, NY, 253-264. · Zbl 1282.68131 |