Gotowe bibliografie tematyczne / K-clique problem

Spis treści

  1. Artykuły w czasopismach
  2. Rozprawy doktorskie
  3. Części książek
  4. Streszczenia konferencji

Gotowa bibliografia na temat „K-clique problem”

Autor: Grafiati
Data publikacji: 6 września 2023

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Zobacz listy aktualnych artykułów, książek, rozpraw, streszczeń i innych źródeł naukowych na temat „K-clique problem”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Artykuły w czasopismach na temat "K-clique problem"

1

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
2

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
3

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
4

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
5

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
6

Wu, Jun, i 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, nr 11 (28.06.2022): 13083–84. http://dx.doi.org/10.1609/aaai.v36i11.21678.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
7

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
8

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
9

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
10

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
Więcej źródeł

Rozprawy doktorskie na temat "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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.

Części książek na temat "K-clique problem"

1

Katayama, Kengo, Masashi Sadamatsu i Hiroyuki Narihisa. "Iterated k-Opt Local Search for the Maximum Clique Problem". W 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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
2

Hifi, Mhand, Ibrahim Moussa, Toufik Saadi i Sagvan Saleh. "An Adaptive Neighborhood Search for k-Clustering Minimum Bi-clique Completion Problems". W 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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
3

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.

Streszczenia konferencji na temat "K-clique problem"

1

Tsourakakis, Charalampos. "The K-clique Densest Subgraph Problem". W 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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
2

Wu, Jun, Chu-Min Li, Yupeng Zhou, Minghao Yin, Xin Xu i Dangdang Niu. "HEA-D: A Hybrid Evolutionary Algorithm for Diversified Top-k Weight Clique Search Problem". W 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.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
3

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
4

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
5

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
6

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
7

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

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
8

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

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
9

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

Pełny tekst źródła
Streszczenie:
Seja G = (V, A) um grafo orientado. O número cromático orientado de G denotado por χo(G) é um parâmetro bem conhecido na literatura. O número clique orientado absoluto, ωao(G), é a ordem do maior subgrafo H de G tal que χo(H) = |V(H)|. Neste trabalho mostramos que decidir se ωao(G) ≤ k é um problema NP-completo e que não existe um algoritmo aproximativo de tempo polinomial com um fator n{1 - ε} para todo ε > 0, a não ser que P = NP.
Style APA, Harvard, Vancouver, ISO itp.
10

Gao, Jian, Jiejiang Chen, Minghao Yin, Rong Chen i Yiyuan Wang. "An Exact Algorithm for Maximum k-Plexes in Massive Graphs". W 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.

Pełny tekst źródła
Streszczenie:
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.
Style APA, Harvard, Vancouver, ISO itp.
Możesz być także zainteresowany rozszerzonymi bibliografiami na temat „K-clique problem” dla poszczególnych typów źródeł:
Artykuły w czasopismach
Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!

Do bibliografii