Log in

Relevant bibliographies by topics / K-clique problem

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'K-clique problem'

Author: Grafiati

Published: 6 September 2023

Last updated: 31 July 2025

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 'K-clique problem.'

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 "K-clique problem"

1

Lee, Chuan-Min. "Exploring Clique Transversal Variants on Distance-Hereditary Graphs: Computational Insights and Algorithmic Approaches." Algorithms 17, no. 8 (2024): 359. http://dx.doi.org/10.3390/a17080359.

Full text

Abstract:

The clique transversal problem is a critical concept in graph theory, focused on identifying a minimum subset of vertices that intersects all maximal cliques in a graph. This problem and its variations—such as the k-fold clique, {k}-clique, minus clique, and signed clique transversal problems—have received significant interest due to their theoretical importance and practical applications. This paper examines the k-fold clique, {k}-clique, minus clique, and signed clique transversal problems on distance-hereditary graphs. Known for their distinctive structural properties, distance hereditary g

APA, Harvard, Vancouver, ISO, and other styles

2

Wu, Jun, and Minghao Yin. "A Restart Local Search for Solving Diversified Top-k Weight Clique Search Problem." Mathematics 9, no. 21 (2021): 2674. http://dx.doi.org/10.3390/math9212674.

Full text

Abstract:

Diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with practical applications. The diversified top-k weight clique search problem aims to search k maximal cliques that can cover the maximum weight in a vertex weighted graph. In this work, we propose a novel local search algorithm called TOPKWCLQ for the DTKWC search problem which mainly includes two strategies. First, a restart strategy is adopted, which repeated the construction and updating processes of the maximal weight clique set. Second, a scoring h

APA, Harvard, Vancouver, ISO, and other styles

3

Lee, Chuan-Min. "Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs." Algorithms 14, no. 1 (2021): 22. http://dx.doi.org/10.3390/a14010022.

Full text

Abstract:

This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the {k}-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {k}-clique transversal problem is polynomial-time solvable for gra

APA, Harvard, Vancouver, ISO, and other styles

4

Zhou, Yingli, Qingshuo Guo, Yixiang Fang, and Chenhao Ma. "A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery." Proceedings of the ACM on Management of Data 2, no. 3 (2024): 1–27. http://dx.doi.org/10.1145/3654922.

Full text

Abstract:

Densest subgraph discovery (DSD) is a fundamental topic in graph mining. It has been extensively studied in the literature and has found many real applications in a wide range of fields, such as biology, finance, and social networks. As a typical problem of DSD, the k-clique densest subgraph (CDS) problem aims to detect a subgraph from a graph, such that the ratio of the number of k-cliques over the number of its vertices is maximized. This problem has received plenty of attention in the literature, and is widely used in identifying larger ''near-cliques''. Existing CDS solutions, either k-cor

APA, Harvard, Vancouver, ISO, and other styles

5

Sanei-Mehri, Seyed-Vahid, Apurba Das, Hooman Hashemi, and Srikanta Tirthapura. "Mining Largest Maximal Quasi-Cliques." ACM Transactions on Knowledge Discovery from Data 15, no. 5 (2021): 1–21. http://dx.doi.org/10.1145/3446637.

Full text

Abstract:

Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Enumerating quasi-cliques from a graph is a robust way to detect densely connected structures with applications in bioinformatics and social network analysis. However, enumerating quasi-cliques in a graph is a challenging problem, even harder than the problem of enumerating cliques. We consider the enumeration of top- k degree-based quasi-cliques and make the following contributions: (1) we show that even the problem of detecting whether a given quasi-clique is maximal (i.e., not contained within ano

APA, Harvard, Vancouver, ISO, and other styles

6

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

7

Szabó, Sándor, and Bogdán Zaválnij. "Clique Search in Graphs of Special Class and Job Shop Scheduling." Mathematics 10, no. 5 (2022): 697. http://dx.doi.org/10.3390/math10050697.

Full text

Abstract:

In this paper, we single out the following particular case of the clique search problem. The vertices of the given graph are legally colored with k colors and we are looking for a clique with k nodes in the graph. In other words, we want to decide if a given k-partite graph contains a clique with k nodes. The maximum clique problem asks for finding a maximum clique in a given finite simple graph. The problem of deciding if the given graph contains a clique with k vertices is called the k-clique problem. The first problem is NP-hard and the second one is NP-complete. The special clique search p

APA, Harvard, Vancouver, ISO, and other styles

8

Wu, Jun, and Minghao Yin. "A Hybrid Evolutionary Algorithm for the Diversified Top-k Weight Clique Search Problem (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 11 (2022): 13083–84. http://dx.doi.org/10.1609/aaai.v36i11.21678.

Full text

Abstract:

The diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique search problem, which extends the DTKC search problem by taking into account the weight of vertices. This problem involves finding at most k maximal weighted cliques that cover maximum weight of vertices with low overlapping in a given graph. In this study, a mixed integer linear program constraint formulation is proposed to model DTKWC search problem and an efficient hybrid evolutionary algorithm (HEA-D) based on some heuristic strategies is proposed to tackle it. Experime

APA, Harvard, Vancouver, ISO, and other styles

9

Conte, Alessio, Donatella Firmani, Maurizio Patrignani, and Riccardo Torlone. "A meta-algorithm for finding large k-plexes." Knowledge and Information Systems 63, no. 7 (2021): 1745–69. http://dx.doi.org/10.1007/s10115-021-01570-8.

Full text

Abstract:

AbstractWe focus on the automatic detection of communities in large networks, a challenging problem in many disciplines (such as sociology, biology, and computer science). Humans tend to associate to form families, villages, and nations. Similarly, the elements of real-world networks naturally tend to form highly connected groups. A popular model to represent such structures is the clique, that is, a set of fully interconnected nodes. However, it has been observed that cliques are too strict to represent communities in practice. The k-plex relaxes the notion of clique, by allowing each node to

APA, Harvard, Vancouver, ISO, and other styles

10

DEKEL, YAEL, ORI GUREL-GUREVICH, and YUVAL PERES. "Finding Hidden Cliques in Linear Time with High Probability." Combinatorics, Probability and Computing 23, no. 1 (2013): 29–49. http://dx.doi.org/10.1017/s096354831300045x.

Full text

Abstract:

We are given a graph G with n vertices, where a random subset of k vertices has been made into a clique, and the remaining edges are chosen independently with probability $\frac12$. This random graph model is denoted $G(n,\frac12,k)$. The hidden clique problem is to design an algorithm that finds the k-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov [3] uses spectral techniques to find the hidden clique with high probability when $k = c \sqrt{n}$ for a sufficiently large constant c > 0. Recently, an algorithm that solves the same problem wa

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "K-clique problem"

1

Trukhanov, Svyatoslav. "Novel approaches for solving large-scale optimization problems on graphs." [College Station, Tex. : Texas A&M University, 2008. http://hdl.handle.net/1969.1/ETD-TAMU-2986.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

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 "K-clique problem"

1

Katayama, Kengo, Masashi Sadamatsu, and Hiroyuki Narihisa. "Iterated k-Opt Local Search for the Maximum Clique Problem." In Evolutionary Computation in Combinatorial Optimization. Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-71615-0_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hifi, Mhand, Ibrahim Moussa, Toufik Saadi, and Sagvan Saleh. "An Adaptive Neighborhood Search for k-Clustering Minimum Bi-clique Completion Problems." In Advances in Intelligent Systems and Computing. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-18161-5_2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Alves, Sancrey Rodrigues, Fernanda Couto, Luerbio Faria, Sylvain Gravier, Sulamita Klein, and Uéverton S. Souza. "Graph Sandwich Problem for the Property of Being Well-Covered and Partitionable into k Independent Sets and $$\ell $$ Cliques." In LATIN 2020: Theoretical Informatics. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-61792-9_46.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Luo, Chunyu, Yi Zhou, Zhengren Wang, and Mingyu Xiao. "A Faster Branching Algorithm for the Maximum k-Defective Clique Problem." In Frontiers in Artificial Intelligence and Applications. IOS Press, 2024. http://dx.doi.org/10.3233/faia240984.

Full text

Abstract:

A k-defective clique of an undirected graph G is a subset of its vertices that induces a nearly complete graph with a maximum of k missing edges. The maximum k-defective clique problem, which asks for the largest k-defective clique from the given graph, is important in many applications, such as social and biological network analysis. In the paper, we propose a new branching algorithm that takes advantage of the structural properties of the k-defective clique and uses the efficient maximum clique algorithm as a subroutine. As a result, the algorithm has a better asymptotic running time than th

APA, Harvard, Vancouver, ISO, and other styles

5

Xue, Jinghui, Jiongzhi Zheng, Kun He, Chu-Min Li, and Yanli Liu. "DiverTEAM: An Effective Evolutionary Algorithm for Diversified Top-k (Weight) Clique Search Problems." In Frontiers in Artificial Intelligence and Applications. IOS Press, 2024. http://dx.doi.org/10.3233/faia240981.

Full text

Abstract:

In many real-world problems and applications, finding only a single element, even though the best, among all possible candidates, cannot fully meet the requirements. We may wish to have a collection where each individual is not only outstanding but also distinctive. Diversified Top-k (DTk) problems are a kind of combinatorial optimization problem for finding such a promising collection of multiple sub-structures, such as subgraphs like cliques and social communities. In this paper, we address two representative DTk problems, DTk Clique search (DTkC) and DTk Weight Clique search (DTkWC), and pr

APA, Harvard, Vancouver, ISO, and other styles

6

Gujjula Krishna Reddy, Ayalur Seshadrinathan Krishnan, and Meisami Amirhossein. "A Hybrid Metaheuristic for the Maximum k-Plex Problem." In NATO Science for Peace and Security Series - D: Information and Communication Security. IOS Press, 2014. https://doi.org/10.3233/978-1-61499-391-9-83.

Full text

Abstract:

Social network analysis is an area of research that is gathering interest and importance since the turn of the century, especially with increased technology proliferation. Graph theory is predominantly being used in the analysis of social networks. The maximum k-plex problem, which belongs to the category of clique relaxation problems has been studied by researchers in this field. This problem is known to be NP-hard. This paper proposes an amalgamation of a greedy randomized adaptive search procedure and tabu search metaheuristic to solve the problem. The performance of the proposed hybrid met

APA, Harvard, Vancouver, ISO, and other styles

7

Fang Zhiwen, Li Chu-Min, Qiao Kan, Feng Xu, and Xu Ke. "Solving Maximum Weight Clique Using Maximum Satisfiability Reasoning." In Frontiers in Artificial Intelligence and Applications. IOS Press, 2014. https://doi.org/10.3233/978-1-61499-419-0-303.

Full text

Abstract:

Satisfiability (SAT) and maximum satisfiability (MaxSAT) techniques are proved to be powerful in solving combinatorial optimization problems. In this paper, we encode the maximum weight clique (MWC) problem into weighted partial MaxSAT and use MaxSAT techniques to solve it. Concretely, we propose a new algorithm based on MaxSAT reasoning called Top-k failed literal detection to improve the upper bound for MWC, and implement an exact branch-and-bound solver for the MWC problem called MaxWClq based on the Top-k failed literal detection algorithm. To our best knowledge, this is the first time tha

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "K-clique problem"

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

Wu, Jun, Chu-Min Li, Yupeng Zhou, Minghao Yin, Xin Xu, and Dangdang Niu. "HEA-D: A Hybrid Evolutionary Algorithm for Diversified Top-k Weight Clique Search Problem." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/668.

Full text

Abstract:

The diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with extensive applications, which extends the DTKC search problem by taking into account the weight of vertices. In this paper, we formulate DTKWC search problem using mixed integer linear program constraints and propose an efficient hybrid evolutionary algorithm (HEA-D) that combines a clique-based crossover operator and an effective simulated annealing-based local optimization procedure to find high-quality local optima. The experimental results sho

APA, Harvard, Vancouver, ISO, and other styles

3

Katayama, Kengo, Akihiro Hamamoto, and Hiroyuki Narihisa. "Solving the maximum clique problem by k-opt local search." In the 2004 ACM symposium. ACM Press, 2004. http://dx.doi.org/10.1145/967900.968107.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Soumaya, Lakehal, and Aitzai Abdelhakim. "Branch and Bound for Facility Layout Problem Using Minimum Weighted Clique Problem in Complete K-partite Graph." In the 2017 International Conference. ACM Press, 2017. http://dx.doi.org/10.1145/3175603.3175610.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Tiella, Roberto, and Mariano Ceccato. "Automatic generation of opaque constants based on the k-clique problem for resilient data obfuscation." In 2017 IEEE 24th International Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE, 2017. http://dx.doi.org/10.1109/saner.2017.7884620.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Sun, Rui, Yiyuan Wang, Shimao Wang, Hui Li, Ximing Li, and Minghao Yin. "Nukplex: An Efficient Local Search Algorithm for Maximum K-Plex Problem." In Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/777.

Full text

Abstract:

The maximum k-plex problem (MKPP) is an significant relaxation version of the maximum clique problem with extensive applications. Recently, lots of researchers have proposed many heuristic algorithms based on various methods to solve the MKPP. In this work, to further improve the performance of solving the MKPP, we propose an efficient local search algorithm based on three main ideas. First, we propose a relaxed bounded configuration checking strategy that considers two kinds of historical searching information to relax the restricted strength of configuration checking and the forbidden condit

APA, Harvard, Vancouver, ISO, and other styles

7

de Oliveira Oliveira, Mateus, and Wim Van den Broeck. "Optimal Extended Formulations from Optimal Dynamic Programming Algorithms." In Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/208.

Full text

Abstract:

Vertex Subset Problems (VSPs) are a class of combinatorial optimization problems on graphs where the goal is to find a subset of vertices satisfying a predefined condition. Two prominent approaches for solving VSPs are dynamic programming over tree-like structures, such as tree-decompositions or clique-decompositions, and linear programming. In this work, we establish a sharp connection between both approaches by showing that if a vertex-subset problem Pi admits a solution-preserving dynamic programming algorithm that produces tables of size at most alpha(k,n) when processing a tree decomposit

APA, Harvard, Vancouver, ISO, and other styles

8

Samarawickrama, R. G. L. M., D. N. Ranasinghe, and T. Sritharan. "Vemaque: Approximately verifiable remote computation of k-clique and maximum clique problems." In 2016 Sixteenth International Conference on Advances in ICT for Emerging Regions (ICTer). IEEE, 2016. http://dx.doi.org/10.1109/icter.2016.7829909.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Monteiro, Bruno, and Vinicius Dos Santos. "Equitable Partition of Graphs into Independent Sets and Cliques." In IV Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/etc.2019.6392.

Full text

Abstract:

A graph is (k, l) if its vertex set can be partitioned into k independent sets and l cliques. Deciding if a graph is (k, l) can be seen as a generalization of coloring, since deciding is a graph belongs to (k, 0) corresponds to deciding if a graph is k-colorable. A coloring is equitable if the cardinalities of the color classes differ by at most 1. In this paper, we generalize both the (k, l) and the equitable coloring problems, by showing that deciding whether a given graph can be equitably partitioned into k independent sets and l cliques is solvable in polynomial time if max(k, l) 2, and NP

APA, Harvard, Vancouver, ISO, and other styles

10

Coelho, E. M. M., H. Coelho, L. Faria, M. P. Ferreira, and S. Klein. "O Problema do Número Clique Orientado Absoluto é NP-completo." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.222592.

Full text

Abstract:

Seja G = (V, A) um grafo orientado. O número cromático orientado de G denotado por χo(G) é um parâmetro bem conhecido na literatura. O número clique orientado absoluto, ωao(G), é a ordem do maior subgrafo H de G tal que χo(H) = |V(H)|. Neste trabalho mostramos que decidir se ωao(G) ≤ k é um problema NP-completo e que não existe um algoritmo aproximativo de tempo polinomial com um fator n{1 - ε} para todo ε > 0, a não ser que P = NP.

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!