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

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

Wu, Jun, and Minghao Yin. "A Restart Local Search for Solving Diversified Top-k Weight Clique Search Problem." Mathematics 9, no. 21 (October 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 heuristic is designed by giving different priorities for maximal weight cliques in candidate set. Meanwhile, a constraint model of the DTKWC search problem is constructed such that the research concerns can be evaluated. Experimental results show that the proposed algorithm TOPKWCLQ outperforms than the comparison algorithm on large-scale real-world graphs.

APA, Harvard, Vancouver, ISO, and other styles

2

Lee, Chuan-Min. "Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs." Algorithms 14, no. 1 (January 13, 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 graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs.

APA, Harvard, Vancouver, ISO, and other styles

3

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 (June 26, 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 another quasi-clique) is NP-hard. (2) We present a novel heuristic algorithm K ernel QC to enumerate the k largest quasi-cliques in a graph. Our method is based on identifying kernels of extremely dense subgraphs within a graph, followed by growing subgraphs around these kernels, to arrive at quasi-cliques with the required densities. (3) Experimental results show that our algorithm accurately enumerates quasi-cliques from a graph, is much faster than current state-of-the-art methods for quasi-clique enumeration (often more than three orders of magnitude faster), and can scale to larger graphs than current methods.

APA, Harvard, Vancouver, ISO, and other styles

4

Sun, Bintao, Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. "KClist++." Proceedings of the VLDB Endowment 13, no. 10 (June 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 with larger values of k can effectively find quasi-cliques. The densest subgraph problem can be solved in polynomial time with algorithms based on maximum flow, linear programming or a recent approach based on convex optimization. In particular, the latter approach can scale to graphs containing tens of billions of edges. While finding a densest subgraph in large graphs is no longer a bottleneck, the k -clique densest subgraph remains challenging even when k = 3. Our work aims at developing near-optimal and exact algorithms for the k -clique densest subgraph problem on large real-world graphs. We give a surprisingly simple procedure that can be employed to find the maximal k -clique densest subgraph in large-real world graphs. By leveraging appealing properties of existing results, we combine it with a recent approach for listing all k -cliques in a graph and a sampling scheme, obtaining the state-of-the-art approaches for the aforementioned problem. Our theoretical results are complemented with an extensive experimental evaluation showing the effectiveness of our approach in large real-world graphs.

APA, Harvard, Vancouver, ISO, and other styles

5

Szabó, Sándor, and Bogdán Zaválnij. "Clique Search in Graphs of Special Class and Job Shop Scheduling." Mathematics 10, no. 5 (February 23, 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 problem, we propose, is still an NP-complete problem. We will show that the k-clique problem in the special case of k-partite graphs is more tractable than in the general case. In order to illustrate the possible practical utility of this restricted type clique search problem we will show that the job shop scheduling problem can be reduced to such a clique search problem in a suitable constructed graph. We carry out numerical experiments to assess the efficiency of the approach. It is a common practice that before one embarks on a large scale clique search typically one attempts to simplify and tidy up the given graph. This procedure is commonly referred as preconditioning or kernelization of the given graph. Of course, the preconditioning or kernelization is meant with respect to the given type of clique search problem. The other main topic of the paper is to describe a number of kernelization methods tailored particularly to the proposed special k-clique problem. Some of these techniques works in connection with the generic k-clique problem. In these situations, we will see that they are more efficient in the case of k-partite graphs. Some other preconditioning methods applicable only to k-partite graphs. We illustrate how expedient these preconditioning methods can be by solving non-trivial scheduling problems to optimality employing only kernelization techniques dispensing with exhaustive clique search algorithms altogether.

APA, Harvard, Vancouver, ISO, and other styles

6

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 (June 28, 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. Experiments on two sets of 110 graphs show that HEA-D outperforms the state-of-art methods.

APA, Harvard, Vancouver, ISO, and other styles

7

Conte, Alessio, Donatella Firmani, Maurizio Patrignani, and Riccardo Torlone. "A meta-algorithm for finding large k-plexes." Knowledge and Information Systems 63, no. 7 (May 1, 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 miss up to k connections. Although k-plexes are more flexible than cliques, finding them is more challenging as their number is greater. In addition, most of them are small and not significant. In this paper we tackle the problem of finding only large k-plexes (i.e., comparable in size to the largest clique) and design a meta-algorithm that can be used on top of known enumeration algorithms to return only significant k-plexes in a fraction of the time. Our approach relies on: (1) methods for strongly reducing the search space and (2) decomposition techniques based on the efficient computation of maximal cliques. We demonstrate experimentally that known enumeration algorithms equipped with our approach can run orders of magnitude faster than full enumeration.

APA, Harvard, Vancouver, ISO, and other styles

8

DEKEL, YAEL, ORI GUREL-GUREVICH, and YUVAL PERES. "Finding Hidden Cliques in Linear Time with High Probability." Combinatorics, Probability and Computing 23, no. 1 (November 14, 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 was proposed by Feige and Ron [12]. It has the advantages of being simpler and more intuitive, and of an improved running time of O(n2). However, the analysis in [12] gives a success probability of only 2/3. In this paper we present a new algorithm for finding hidden cliques that both runs in time O(n2) (that is, linear in the size of the input) and has a failure probability that tends to 0 as n tends to ∞. We develop this algorithm in the more general setting where the clique is replaced by a dense random graph.

APA, Harvard, Vancouver, ISO, and other styles

9

McCreesh, Ciaran, and Patrick Prosser. "Finding Maximum k-Cliques Faster Using Lazy Global Domination." Proceedings of the International Symposium on Combinatorial Search 7, no. 1 (September 1, 2021): 72–80. http://dx.doi.org/10.1609/socs.v7i1.18387.

Full text

Abstract:

A clique in a graph is a set of vertices, each of which is adjacent to every other vertex in this set. A k-clique relaxes this requirement, requiring vertices to be within a distance k of each other, rather than directly adjacent. In theory, a maximum clique algorithm can easily be adapted to solve the maximum k-clique problem, although large sparse k-clique graphs reduce to large dense clique graphs, which can be computationally challenging. We adapt a state of the art maximum clique algorithm to show that this reduction is in fact useful in practice, and introduce a lazy global domination rule which sometimes vastly reduces the search space. We include experimental results for a range of real-world and benchmark graphs, and a detailed look at random graphs. We also use thread-parallel search to solve some harder instances.

APA, Harvard, Vancouver, ISO, and other styles

10

Goldschmidt, Oliver, Dorit S. Hochbaum, Cor Hurkens, and Gang Yu. "Approximation Algorithms for the k-Clique Covering Problem." SIAM Journal on Discrete Mathematics 9, no. 3 (August 1996): 492–509. http://dx.doi.org/10.1137/s089548019325232x.

Full text

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

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, 84–95. Berlin, Heidelberg: 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, 15–25. Cham: 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, 587–99. Cham: 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

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. Republic and Canton of Geneva, Switzerland: 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}. California: 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 show that HEA-D performs much better than the existing methods on two representative real-world benchmarks.

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. New York, New York, USA: 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. New York, New York, USA: 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

Alves, S. R., F. Couto, L. Faria, S. Klein, and U. dos S. Souza. "O problema probe particionado split bem-coberto é polinomial." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3170.

Full text

Abstract:

Um grafo G = (V, E) é bem-coberto se cada conjunto independente maximal de G é máximo. Um grafo G = (V, E) é split se existe uma partição V = (S, K), onde S é um conjunto independente e K é uma clique. Um grafo split bem-coberto é, ao mesmo tempo, split e bem-coberto. Dada uma classe C de grafos, um grafo G = (V, E) é C probe se existe uma partição para V = (N, P ) em probes P e não-probes N , onde N é um conjunto independente e novas arestas podem ser adicionadas entre não-probes de maneira que o grafo resultante permaneça na classe de grafos C. Dizemos que (N, P ) é uma C probe partição para G. O problema C PROBE PARTICIONADO consiste de um grafo de entrada G e uma partição probe V = (N, P ) e a questão: (N, P ) é uma C partição probe? Neste artigo, consideramos C como a classe dos grafos split bem-cobertos, e provamos que o problema C PROBE PARTICIONADO pertence à classe de problemas polinomiais P.

APA, Harvard, Vancouver, ISO, and other styles

7

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

8

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 complete otherwise.

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

Gao, Jian, Jiejiang Chen, Minghao Yin, Rong Chen, and Yiyuan Wang. "An Exact Algorithm for Maximum k-Plexes in Massive Graphs." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/201.

Full text

Abstract:

The maximum k-plex, a generalization of maximum clique, is used to cope with a great number of real-world problems. The aim of this paper is to propose a novel exact k-plex algorithm that can deal with large-scaled graphs with millions of vertices and edges. Specifically, we first propose several new graph reduction methods through a careful analyzing of structures of induced subgraphs. Afterwards, we present a preprocessing method to simplify initial graphs. Additionally, we present a branch-and-bound algorithm integrating the reduction methods as well as a new dynamic vertex selection mechanism. We perform intensive experiments to evaluate our algorithm, and show that the proposed strategies are effective and our algorithm outperforms state-of-the-art algorithms, especially for real-world massive graphs.

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!