Fast quasi-threshold editing. (English) Zbl 1465.68209
Bansal, Nikhil (ed.) et al., Algorithms – ESA 2015. 23rd annual European symposium, Patras, Greece, September 14–16, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9294, 251-262 (2015).
Summary: We introduce quasi-threshold mover (QTM), an algorithm to solve the quasi-threshold (also called trivially perfect) graph editing problem with a minimum number of edge insertions and deletions. Given a graph it computes a quasi-threshold graph which is close in terms of edit count, but not necessarily closest as this edit problem is NP-hard. We present an extensive experimental study, in which we show that QTM performs well in practice and is the first heuristic that is able to scale to large real-world graphs in practice. As a side result we further present a simple linear-time algorithm for the quasi-threshold recognition problem.
For the entire collection see [Zbl 1320.68011].
For the entire collection see [Zbl 1320.68011].
References:
| [1] | Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: Graph Partitioning and Graph Clustering: 10th DIMACS Implementation Challenge, vol. 588. American Mathematical Society (2013) · Zbl 1262.05001 · doi:10.1090/conm/588 |
| [2] | Blondel, V., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008(10) (2008) · doi:10.1088/1742-5468/2008/10/P10008 |
| [3] | Boldi, P., Codenotti, B., Santini, M., Vigna, S.: Ubicrawler: A scalable fully distributed web crawler. Software - Practice and Experience 34(8), 711–726 (2004) · doi:10.1002/spe.587 |
| [4] | Boldi, P., Rosa, M., Santini, M., Vigna, S.: Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In: Proceedings of the 20th International Conference on World Wide Web (WWW 2011), pp. 587–596. ACM Press (2011) · doi:10.1145/1963405.1963488 |
| [5] | Boldi, P., Vigna, S.: The WebGraph framework I: Compression techniques. In: Proceedings of the 13th International Conference on World Wide Web (WWW 2004), pp. 595–602. ACM Press (2004) · doi:10.1145/988672.988752 |
| [6] | Brandes, U., Hamann, M., Strasser, B., Wagner, D.: Fast quasi-threshold editing (2015), http://arxiv.org/abs/1504.07379 · Zbl 1465.68209 |
| [7] | Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters 58(4), 171–176 (1996) · Zbl 0875.68702 · doi:10.1016/0020-0190(96)00050-6 |
| [8] | Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM Journal on Computing 14(1), 210–223 (1985) · Zbl 0572.68053 · doi:10.1137/0214017 |
| [9] | Chu, F.P.M.: A simple linear time certifying lbfs-based algorithm for recognizing trivially perfect graphs and their complements. Information Processing Letters 107(1), 7–12 (2008) · Zbl 1185.05134 · doi:10.1016/j.ipl.2007.12.009 |
| [10] | Drange, P.G., Dregi, M.S., Lokshtanov, D., Sullivan, B.D.: On the threshold of intractability. In: Proceedings of the 23rd Annual European Symposium on Algorithms (ESA 2015). LNCS. Springer (2015) · Zbl 1466.68042 · doi:10.1007/978-3-662-48350-3_35 |
| [11] | Drange, P.G., Pilipczuk, M.: A polynomial kernel for trivially perfect editing. In: Proceedings of the 23rd Annual European Symposium on Algorithms (ESA 2015). LNCS. Springer (2015) · Zbl 1466.68045 · doi:10.1007/978-3-662-48350-3_36 |
| [12] | Görke, R., Kappes, A., Wagner, D.: Experiments on density-constrained graph clustering. ACM Journal of Experimental Algorithmics 19, 1.6:1.1–1.6:1.31 (2014) · Zbl 1347.68310 |
| [13] | Leskovec, J., Krevl, A.: Snap datasets: Stanford large network dataset collection (June 2014), http://snap.stanford.edu/data |
| [14] | Nastos, J., Gao, Y.: Familial groups in social networks. Social Networks 35(3), 439–450 (2013) |
| [15] | Ortmann, M., Brandes, U.: Triangle listing algorithms: Back from the diversion. In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX 2014), pp. 1–8. SIAM (2014) · doi:10.1137/1.9781611973198.1 |
| [16] | Rotta, R., Noack, A.: Multilevel local search algorithms for modularity clustering. ACM Journal of Experimental Algorithmics 16, 2.3:2.1–2.3:2.27 (2011) · Zbl 1284.05309 |
| [17] | Staudt, C., Sazonovs, A., Meyerhenke, H.: Networkit: An interactive tool suite for high-performance network analysis (2014), http://arxiv.org/abs/1403.3005 |
| [18] | Traud, A.L., Mucha, P.J., Porter, M.A.: Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications 391(16), 4165–4180 (2012) · doi:10.1016/j.physa.2011.12.021 |
| [19] | Wolk, E.S.: A note on ”the comparability graph of a tree”. Proceedings of the American Mathematical Society 16(1), 17–20 (1965) · Zbl 0137.18105 |
| [20] | Yan, J.H., Chen, J.J., Chang, G.J.: Quasi-threshold graphs. Discrete Applied Mathematics 69(3), 247–255 (1996) · Zbl 0857.05082 · doi:10.1016/0166-218X(96)00094-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
