Certifying Fully Dynamic Algorithms for Recognition and Hamiltonicity of Threshold and Chain Graphs

Beisegel, J., Chiarelli, N., Köhler, E., Krnc, M., Milanič, M., Pivač, N., Scheffler, R., Strehler, M.: Edge elimination and weighted graph classes. In: Adler, I., Müller, H. (eds.) Graph-Theoretic Concepts in Computer Science, LNCS, vol. 12301, pp. 134–147. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60440-0_11

Bhattacharya, S., Henzinger, M., Nanongkai, D.: New deterministic approximation algorithms for fully dynamic matching. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pp. 398–411 (2016). https://doi.org/10.1145/2897518.2897568

Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM (1999). https://doi.org/10.1137/1.9780898719796

Calamoneri, T., Monti, A., Petreschi, R.: Fully dynamically maintaining minimal integral separator for threshold and difference graphs. In: WALCOM: Algorithms and Computation, LNCS, vol. 9627, pp. 313–324. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30139-6_25

Chvátal, V., Hammer, P.L.: Set-packing and threshold graphs. Tech. Rep. CORR 73-21, University of Waterloo (1973)

Chvátal, V., Hammer, P.L.: Aggregations of inequalities in integer programming. Stud. Integ. Program. Ann. Discrete Math. 1, 145–162 (1977)

Cozzens, M.B., Leibowitz, R.: Threshold dimension of graphs. SIAM J. Algebr. Discrete Methods 5, 579–595 (1984). https://doi.org/10.1137/0605055

Cozzens, M.B., Leibowitz, R.: Multidimensional scaling and threshold graphs. J. Math. Psychol. 31, 179–191 (1987). https://doi.org/10.1016/0022-2496(87)90014-9

Crespelle, C., Paul, C.: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs. Algorithmica 58(2), 405–432 (2010). https://doi.org/10.1007/s00453-008-9273-0

Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic shortest paths in digraphs with arbitrary arc weights. J. Algorithms 49(1), 86–113 (2003). https://doi.org/10.1016/S0196-6774(03)00082-8

Hammer, P.L., Peled, U.N., Sun, X.: Difference graphs. Discrete Appl. Math. 28(1), 35–44 (1990). https://doi.org/10.1016/0166-218X(90)90092-Q

Harary, F., Peled, U.: Hamiltonian threshold graphs. Discrete Appl. Math. 16, 11–15 (1987). https://doi.org/10.1016/0166-218X(87)90050-3

Heggernes, P., Kratsch, D.: Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic J. Comput. 14(1–2), 87–108 (2007)

Heggernes, P., Papadopoulos, C.: Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. In: International Computing and Combinatorics Conference, pp. 406–416. Springer (2007). https://doi.org/10.1007/978-3-540-73545-8_40

Heggernes, P., Papadopoulos, C.: Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. Theor. Comput. Sci. 410(1), 1–15 (2009). https://doi.org/10.1016/j.tcs.2008.07.020

Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput. 31(1), 289–305 (2002). https://doi.org/10.1137/S0097539700372216

Henderson, P.B., Zalcstein, Y.: A graph-theoretic characterization of the $$\text{ PV}_{\text{ chunk }}$$ class of synchronizing primitives. SIAM J. Comput. 6(1), 88–108 (1977). https://doi.org/10.1137/0206008

Henzinger, M.R.: Fully dynamic biconnectivity in graphs. Algorithmica 13(6), 503–538 (1995). https://doi.org/10.1007/BF01189067

Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351–362 (1998). https://doi.org/10.1007/PL00009228

Ibarra, L.: Fully dynamic algorithms for chordal graphs and split graphs. ACM Trans. Algorithms 4(4), 1–40 (2008). https://doi.org/10.1145/1383369.1383371

Klein, P.N., Subramanian, S.: A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 22(3), 235–249 (1998). https://doi.org/10.1007/PL00009223

Koop, G.J.: Cyclic scheduling of offweekends. Oper. Res. Lett. 4, 259–263 (1986). https://doi.org/10.1016/0167-6377(86)90026-X

Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics. Annals of Discrete Mathematics, vol. 56. North-Holland Publishing Co., Amsterdam (1995)

Ordman, E.T.: Threshold coverings and resource allocation. In: Proceedings of the 16th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 99–113. Utilitas Mathematica Pub., Winnipeg (1985)

Ordman, E.T.: Minimal threshold separators and memory requirements for synchronization. SIAM J. Comput. 18(1), 152–165 (1989). https://doi.org/10.1137/0218010

Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266–283 (1976). https://doi.org/10.1137/0205021

Shamir, R., Sharan, R.: A fully dynamic algorithm for modular decomposition and recognition of cographs. Discrete Appl. Math. 136(2–3), 329–340 (2004). https://doi.org/10.1016/S0166-218X(03)00448-7

Soulignac, F.J.: Fully dynamic recognition of proper circular-arc graphs. Algorithmica 71(4), 904–968 (2015). https://doi.org/10.1007/s00453-013-9835-7

Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 343–350 (2000). https://doi.org/10.1145/335305.335345

Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebr. Discrete Methods 3(3), 351–358 (1982). https://doi.org/10.1137/0603036