Log in

Relevant bibliographies by topics / Densest k-subgraph

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'Densest k-subgraph'

Author: Grafiati

Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Densest k-subgraph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Densest k-subgraph"

1

Sun, Bintao, Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. "KClist++." Proceedings of the VLDB Endowment 13, no. 10 (2020): 1628–40. http://dx.doi.org/10.14778/3401960.3401962.

Full text

Abstract:

The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology, finance, as well as social network analysis. The k -clique densest subgraph problem is a generalization of the densest subgraph problem, where the objective is to find a subgraph maximizing the ratio between the number of k -cliques in the subgraph and its number of nodes. It includes as a special case the problem of finding subgraphs with largest average number of triangles ( k = 3), which plays an important role in social network analysis. Moreover, algorithms that deal

APA, Harvard, Vancouver, ISO, and other styles

2

Calude, Cristian S., Michael J. Dinneen, and Richard Hua. "Quantum solutions for densest k-subgraph problems." Journal of Membrane Computing 2, no. 1 (2020): 26–41. http://dx.doi.org/10.1007/s41965-019-00030-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Nonner, Tim. "PTAS for Densest $$k$$ k -Subgraph in Interval Graphs." Algorithmica 74, no. 1 (2014): 528–39. http://dx.doi.org/10.1007/s00453-014-9956-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Liazi, Maria, Ioannis Milis, Fanny Pascual, and Vassilis Zissimopoulos. "The densest k-subgraph problem on clique graphs." Journal of Combinatorial Optimization 14, no. 4 (2007): 465–74. http://dx.doi.org/10.1007/s10878-007-9069-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Rozenshtein, Polina, Francesco Bonchi, Aristides Gionis, Mauro Sozio, and Nikolaj Tatti. "Finding events in temporal networks: segmentation meets densest subgraph discovery." Knowledge and Information Systems 62, no. 4 (2019): 1611–39. http://dx.doi.org/10.1007/s10115-019-01403-9.

Full text

Abstract:

Abstract In this paper, we study the problem of discovering a timeline of events in a temporal network. We model events as dense subgraphs that occur within intervals of network activity. We formulate the event discovery task as an optimization problem, where we search for a partition of the network timeline into k non-overlapping intervals, such that the intervals span subgraphs with maximum total density. The output is a sequence of dense subgraphs along with corresponding time intervals, capturing the most interesting events during the network lifetime. A naïve solution to our optimization

APA, Harvard, Vancouver, ISO, and other styles

6

Roupin, Frederic, and Alain Billionnet. "A deterministic approximation algorithm for the Densest k-Subgraph Problem." International Journal of Operational Research 3, no. 3 (2008): 301. http://dx.doi.org/10.1504/ijor.2008.017534.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Sotirov, Renata. "On solving the densest k-subgraph problem on large graphs." Optimization Methods and Software 35, no. 6 (2019): 1160–78. http://dx.doi.org/10.1080/10556788.2019.1595620.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Guo, Chuan-Hao, Yuan Guo, and Bei-Bei Liu. "Doubly Nonnegative and Semidefinite Relaxations for the Densest k-Subgraph Problem." Entropy 21, no. 2 (2019): 108. http://dx.doi.org/10.3390/e21020108.

Full text

Abstract:

The densest k-subgraph (DkS) maximization problem is to find a set of k vertices with maximum total weight of edges in the subgraph induced by this set. This problem is in general NP-hard. In this paper, two relaxation methods for solving the DkS problem are presented. One is doubly nonnegative relaxation, and the other is semidefinite relaxation with tighter relaxation compare with the relaxation of standard semidefinite. The two relaxation problems are equivalent under the suitable conditions. Moreover, the corresponding approximation ratios’ results are given for these relaxation problems.

APA, Harvard, Vancouver, ISO, and other styles

9

Xu, Yichen, Chenhao Ma, Yixiang Fang, and Zhifeng Bao. "Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery." Proceedings of the ACM on Management of Data 1, no. 2 (2023): 1–27. http://dx.doi.org/10.1145/3589314.

Full text

Abstract:

The densest subgraph problem (DSP) is of great significance due to its wide applications in different domains. Meanwhile, diverse requirements in various applications lead to different density variants for DSP. Unfortunately, existing DSP algorithms cannot be easily extended to handle those variants efficiently and accurately. To fill this gap, we first unify different density metrics into a generalized density definition. We further propose a new model, c-core, to locate the general densest subgraph and show its advantage in accelerating the searching process. Extensive experiments show that

APA, Harvard, Vancouver, ISO, and other styles

10

Konar, Aritra, and Nicholas D. Sidiropoulos. "The Triangle-Densest-K-Subgraph Problem: Hardness, Lovász Extension, and Application to Document Summarization." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 4 (2022): 4075–82. http://dx.doi.org/10.1609/aaai.v36i4.20325.

Full text

Abstract:

We introduce the triangle-densest-K-subgraph problem (TDKS) for undirected graphs: given a size parameter K, compute a subset of K vertices that maximizes the number of induced triangles. The problem corresponds to the simplest generalization of the edge based densest-K-subgraph problem (DKS) to the case of higher-order network motifs. We prove that TDKS is NP-hard and is not amenable to efficient approximation, in the worst-case. By judiciously exploiting the structure of the problem, we propose a relaxation algorithm for the purpose of obtaining high-quality, sub-optimal solutions. Our appro

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Densest k-subgraph"

1

Wu, Yubao. "Efficient and Effective Local Algorithms for Analyzing Massive Graphs." Case Western Reserve University School of Graduate Studies / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=case1454451336.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Sariyuce, Ahmet Erdem. "Fast Algorithms for Large-Scale Network Analytics." The Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1429825578.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Khanna, Yash. "Robust Algorithms for recovering planted structures in Semi-random instances." Thesis, 2021. https://etd.iisc.ac.in/handle/2005/5096.

Full text

Abstract:

In this thesis, we study algorithms for three fundamental graph problems. These are NP-hard problems which have not been understood completely as there is a signifiicant gap between the algorithmic and the hardness fronts or the hardness factor in the worst-case is pretty large. Thus it is natural to study them in random and semi-random models. This falls under the area of "Beyond worst-case Analysis". We describe these problems now. In the first part, we study the Densest k-subgraph problem (DkS). Given an undirected graph G, the DkS problem asks to compute a set S \subseteq V of cardinal

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Densest k-subgraph"

1

Chen, Danny Z., Rudolf Fleischer, and Jian Li. "Densest k-Subgraph Approximation on Intersection Graphs." In Approximation and Online Algorithms. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-18318-8_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Bourgeois, Nicolas, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, and Vangelis Th Paschos. "Exact and Approximation Algorithms for Densest k-Subgraph." In WALCOM: Algorithms and Computation. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-36065-7_12.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Nonner, Tim. "PTAS for Densest k-Subgraph in Interval Graphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22300-6_53.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Gonzales, Sean, and Theresa Migler. "The Densest k Subgraph Problem in b-Outerplanar Graphs." In Complex Networks and Their Applications VIII. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-36687-2_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Zhang, Peng, and Zhendong Liu. "Approximating Max k-Uncut via LP-rounding Plus Greed, with Applications to Densest k-Subgraph." In Algorithmic Aspects in Information and Management. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-57602-8_15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Chen, Wenbin, Lingxi Peng, Jianxiong Wang, Fufang Li, and Maobin Tang. "Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset." In Combinatorial Optimization and Applications. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-26626-8_41.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Chen, Xujin, Xiaodong Hu, and Changjun Wang. "Finding Connected Dense $$k$$ -Subgraphs." In Lecture Notes in Computer Science. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-17142-5_22.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Nikolentzos, Giannis, Polykarpos Meladianos, Yannis Stavrakas, and Michalis Vazirgiannis. "K-Clique-Graphs for Dense Subgraph Discovery." In Machine Learning and Knowledge Discovery in Databases. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-71249-9_37.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Dondi, Riccardo, Pietro Hiram Guzzi, and Mohammad Mehdi Hosseinzadeh. "Top-k Connected Overlapping Densest Subgraphs in Dual Networks." In Complex Networks & Their Applications IX. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-65351-4_47.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Valari, Elena, Maria Kontaki, and Apostolos N. Papadopoulos. "Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31235-9_14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Densest k-subgraph"

1

Tsourakakis, Charalampos. "The K-clique Densest Subgraph Problem." In WWW '15: 24th International World Wide Web Conference. International World Wide Web Conferences Steering Committee, 2015. http://dx.doi.org/10.1145/2736277.2741098.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Braverman, Mark, Young Kun Ko, Aviad Rubinstein, and Omri Weinstein. "ETH Hardness for Densest-k-Subgraph with Perfect Completeness." In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017. http://dx.doi.org/10.1137/1.9781611974782.86.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Jones, Chris, Aaron Potechin, Goutham Rajendran, and Jeff Xu. "Sum-of-Squares Lower Bounds for Densest k-Subgraph." In STOC '23: 55th Annual ACM Symposium on Theory of Computing. ACM, 2023. http://dx.doi.org/10.1145/3564246.3585221.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Manurangsi, Pasin. "Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph." In STOC '17: Symposium on Theory of Computing. ACM, 2017. http://dx.doi.org/10.1145/3055399.3055412.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Bhaskara, Aditya, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou. "Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph." In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2012. http://dx.doi.org/10.1137/1.9781611973099.34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Tasnádi, Zoltán, and Noémi Gaskó. "An Ant Colony Optimisation Approach to the Densest k-Subgraph Problem*." In 2022 24th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC). IEEE, 2022. http://dx.doi.org/10.1109/synasc57785.2022.00039.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Huang, Nan. "A QUBO Formulation For the K-densest Common Subgraph Isomorphism Problem Via Quantum Annealing." In 2020 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE). IEEE, 2020. http://dx.doi.org/10.1109/csde50874.2020.9411586.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Chang, Shih-Chia, Li-Hsuan Chen, Ling-Ju Hung, Shih-Shun Kao, and Ralf Klasing. "The Hardness and Approximation of the Densest k-Subgraph Problem in Parameterized Metric Graphs." In 2020 International Computer Symposium (ICS). IEEE, 2020. http://dx.doi.org/10.1109/ics51289.2020.00034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Guo, Chuanhao, and Liping Tang. "A New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph." In 2018 International Conference on Mathematics, Modelling, Simulation and Algorithms (MMSA 2018). Atlantis Press, 2018. http://dx.doi.org/10.2991/mmsa-18.2018.70.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Nasir, Muhammad Anis Uddin, Aristides Gionis, Gianmarco De Francisci Morales, and Sarunas Girdzijauskas. "Fully Dynamic Algorithm for Top- k Densest Subgraphs." In CIKM '17: ACM Conference on Information and Knowledge Management. ACM, 2017. http://dx.doi.org/10.1145/3132847.3132966.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!