Log in

Relevant bibliographies by topics / K-clique problem / Journal articles

To see the other types of publications on this topic, follow the link: K-clique problem.

Journal articles 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 top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

11

Chang, Lijun. "Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance." Proceedings of the VLDB Endowment 18, no. 2 (2024): 200–212. https://doi.org/10.14778/3705829.3705839.

Full text

Abstract:

k -defective clique is a relaxation of the well-studied clique structure, by allowing up-to k edges missing from a clique. The problem of finding a k -defective clique with the largest number of vertices, although being NP-hard, has been receiving increasing interests recently, with advancements in both the theoretical time complexity and practical efficiency. The state-of-the-art time complexity is O*(γ n k ) , where O* ignores polynomial factors, n is the number of vertices in the input graph G , and γ k < 2 is a constant that only depends on k. In this paper, we first prove, through a mo

APA, Harvard, Vancouver, ISO, and other styles

12

Chang, Lijun, Rashmika Gamage, and Jeffrey Xu Yu. "Efficient k -Clique Count Estimation with Accuracy Guarantee." Proceedings of the VLDB Endowment 17, no. 11 (2024): 3707–19. http://dx.doi.org/10.14778/3681954.3682032.

Full text

Abstract:

Counting and enumerating all occurrences of k -cliques, i.e., complete subgraphs with k vertices, in a large graph G is a fundamental problem with many applications. However, exact solutions are often infeasible due to the exponential growth in the number of k -cliques when k increases. Thus, a more practical approach is approximately counting and uniformly sampling k -cliques. Turán-Shadow and DPColorPath are two state-of-the-art algorithms for approximately counting k -cliques. The general idea is first constructing a sample space that is a superset of all k -cliques in G , and then sampling

APA, Harvard, Vancouver, ISO, and other styles

13

Xu, Xiaojia, Haoyu Liu, Xiaowei Lv, Yongcai Wang, and Deying Li. "An Efficient and Exact Algorithm for Locally h -Clique Densest Subgraph Discovery." Proceedings of the ACM on Management of Data 2, no. 6 (2024): 1–26. https://doi.org/10.1145/3698800.

Full text

Abstract:

Detecting locally, non-overlapping, near-clique densest subgraphs is a crucial problem for community search in social networks. As a vertex may be involved in multiple overlapped local cliques, detecting locally densest sub-structures considering h -clique density, i.e., locally h-clique densest subgraph (LhCDS) attracts great interests. This paper investigates the L h CDS detection problem and proposes an efficient and exact algorithm to list the top- k non-overlapping, locally h -clique dense, and compact subgraphs. We in particular jointly consider h -clique compact number and L h CDS and d

APA, Harvard, Vancouver, ISO, and other styles

14

Ambashankar, Akash, and Hovhannes A. Harutyunyan. "Broadcasting in Stars of Cliques and Path-Connected Cliques." Algorithms 18, no. 2 (2025): 76. https://doi.org/10.3390/a18020076.

Full text

Abstract:

Broadcasting is a fundamental information dissemination problem in a connected network where one node, referred to as the originator, must distribute a message to all other nodes through a series of calls along the network’s links. Once informed, nodes assist the originator by forwarding the message to their neighbors. Determining the broadcast time for a node in an arbitrary network is NP-complete. While polynomial-time algorithms exist for specific network topologies, the problem remains open for many others. In this paper, we focus on addressing the broadcasting problem in network topologie

APA, Harvard, Vancouver, ISO, and other styles

15

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 (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 ru

APA, Harvard, Vancouver, ISO, and other styles

16

Suyudi, Mochamad, Asep K. Supriatna, and Sukono Sukono. "Alternative Branching Strategies in the Branch and Bound Algorithm by Using a k-clique covering vertex set for Maximum Clique Problems." International Journal of Quantitative Research and Modeling 1, no. 4 (2020): 208–16. http://dx.doi.org/10.46336/ijqrm.v1i4.82.

Full text

Abstract:

The Maximum clique problem (MCP) is graph theory problem that demand complete subgraf with maximum cardinality (maximum clique) in arbitrary graph. Solving MCP usually use Branch and Bound (BnB) algorithm, in this paper we will show how n + 1 color classes (where n is the difference between upper and lower bound) selected to form k-clique covering vertex set which later used for branching strategy can guarenteed finnding maximum clique.

APA, Harvard, Vancouver, ISO, and other styles

17

Suyudi, Mochamad, Asep K. Supriatna, and Sukono Sukono. "Alternative Branching Strategies in the Branch and Bound Algorithm by Using a k-clique covering vertex set for Maximum Clique Problems." International Journal of Quantitative Research and Modeling 1, no. 4 (2020): 208–16. http://dx.doi.org/10.46336/ijqrm.v1i4.82.

Full text

Abstract:

The Maximum clique problem (MCP) is graph theory problem that demand complete subgraf with maximum cardinality (maximum clique) in arbitrary graph. Solving MCP usually use Branch and Bound (BnB) algorithm, in this paper we will show how n + 1 color classes (where n is the difference between upper and lower bound) selected to form k-clique covering vertex set which later used for branching strategy can guarenteed finnding maximum clique.

APA, Harvard, Vancouver, ISO, and other styles

18

Suyudi, Mochamad, Asep K. Supriatna, and Sukono Sukono. "Alternative Branching Strategies in the Branch and Bound Algorithm by Using a K-Clique Covering Vertex Set for Maximum Clique Problems." International Journal of Quantitative Research and Modeling 1, no. 4 (2020): 208–16. http://dx.doi.org/10.46336/ijqrm.v1i4.92.

Full text

Abstract:

The maximum clique problem (MCP) is graph theory problem that demand complete subgraph with maximum cardinality (maximum clique) in arbitrary graph. Solving MCP usually use Branch and Bound (BnB) algorithm. In this paper, we will show how n + 1 color classes (where n is the difference between upper and lower bound) selected to form k-clique covering vertex set which later used for branching strategy can guarantee finding maximum clique.

APA, Harvard, Vancouver, ISO, and other styles

19

Malod-Dognin, Noël, Rumen Andonov, and Nicola Yanev. "Solving Maximum Clique Problem for Protein Structure Similarity." Serdica Journal of Computing 4, no. 1 (2010): 93–100. http://dx.doi.org/10.55630/sjc.2010.4.93-100.

Full text

Abstract:

Computing the similarity between two protein structures is a crucial task in molecular biology, and has been extensively investigated. Many protein structure comparison methods can be modeled as maximum weighted clique problems in specific k-partite graphs, referred here as alignment graphs. In this paper we present both a new integer programming formulation for solving such clique problems and a dedicated branch and bound algorithm for solving the maximum cardinality clique problem. Both approaches have been integrated in VAST, a software for aligning protein 3D structures largely used in the

APA, Harvard, Vancouver, ISO, and other styles

20

Jin, Mingming, Jiongzhi Zheng, and Kun He. "KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 18 (2024): 20735–42. http://dx.doi.org/10.1609/aaai.v38i18.30061.

Full text

Abstract:

The Maximum k-Defective Clique Problem (MDCP) aims to find a maximum k-defective clique in a given graph, where a k-defective clique is a relaxation clique missing at most k edges. MDCP is NP-hard and finds many real-world applications in analyzing dense but not necessarily complete subgraphs. Exact algorithms for MDCP mainly follow the Branch-and-bound (BnB) framework, whose performance heavily depends on the quality of the upper bound on the cardinality of a maximum k-defective clique. The state-of-the-art BnB MDCP algorithms calculate the upper bound quickly but conservatively as they ignor

APA, Harvard, Vancouver, ISO, and other styles

21

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 (1996): 492–509. http://dx.doi.org/10.1137/s089548019325232x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

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

23

Stern, Roni, Meir Kalech, and Ariel Felner. "Searching for a k-Clique in Unknown Graphs." Proceedings of the International Symposium on Combinatorial Search 1, no. 1 (2010): 83–89. http://dx.doi.org/10.1609/socs.v1i1.18175.

Full text

Abstract:

Agents that solve problems in unknown graphs are usually required to iteratively explore parts of the graph. In this paper we research the problem of finding a k-clique in an unknown graph while minimizing the number of required exploration actions. Two novel heuristics Known Degree and Clique* are proposed to reduce the required exploration cost by carefully choosing which part of the environment to explore. We further investigate the problem by adding probabilistic knowledge of the graph and propose an Markov Decision Process(MDP) and a Monte Carlo based heuristic (RClique*) that uses knowle

APA, Harvard, Vancouver, ISO, and other styles

24

Koh, Yeong Jun, Yuk Heo, and Chang-Su Kim. "Sequential Clique Optimization for Unsupervised and Weakly Supervised Video Object Segmentation." Electronics 11, no. 18 (2022): 2899. http://dx.doi.org/10.3390/electronics11182899.

Full text

Abstract:

A novel video object segmentation algorithm, which segments out multiple objects in a video sequence in unsupervised or weakly supervised manners, is proposed in this work. First, we match visually important object instances to construct salient object tracks through a video sequence without any user supervision. We formulate this matching process as the problem to find maximal weight cliques in a complete k-partite graph and develop the sequential clique optimization algorithm to determine the cliques efficiently. Then, we convert the resultant salient object tracks into object segmentation r

APA, Harvard, Vancouver, ISO, and other styles

25

Dai, Qiangqiang, Ronghua Li, Donghang Cui, and Guoren Wang. "Theoretically and Practically Efficient Maximum Defective Clique Search." Proceedings of the ACM on Management of Data 2, no. 4 (2024): 1–27. http://dx.doi.org/10.1145/3677142.

Full text

Abstract:

The study of k -defective cliques, defined as induced subgraphs that differ from cliques by at most k missing edges, has attracted much attention in graph analysis due to their relevance in various applications, including social network analysis and implicit interaction predictions. However, determining the maximum k -defective clique in graphs has been proven to be an NP-hard problem, presenting significant challenges in finding an efficient solution. To address this problem, we develop a theoretically and practically efficient algorithm that leverages newly-designed branch reduction rules an

APA, Harvard, Vancouver, ISO, and other styles

26

Chang, Lijun. "Efficient Maximum k-Defective Clique Computation with Improved Time Complexity." Proceedings of the ACM on Management of Data 1, no. 3 (2023): 1–26. http://dx.doi.org/10.1145/3617313.

Full text

Abstract:

k-defective cliques relax cliques by allowing up-to k missing edges from being a complete graph. This relaxation enables us to find larger near-cliques and has applications in link prediction, cluster detection, social network analysis and transportation science. The problem of finding the largest k-defective clique has been recently studied with several algorithms being proposed in the literature. However, the currently fastest algorithm KDBB does not improve its time complexity from being the trivial O(2n), and also, KDBB's practical performance is still not satisfactory. In this paper, we a

APA, Harvard, Vancouver, ISO, and other styles

27

Zhou, Yi, Jingwei Xu, Zhenyu Guo, Mingyu Xiao, and Yan Jin. "Enumerating Maximal k-Plexes with Worst-Case Time Guarantee." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 03 (2020): 2442–49. http://dx.doi.org/10.1609/aaai.v34i03.5625.

Full text

Abstract:

The problem of enumerating all maximal cliques in a graph is a key primitive in a variety of real-world applications such as community detection and so on. However, in practice, communities are rarely formed as cliques due to data noise. Hence, k-plex, a subgraph in which any vertex is adjacent to all but at most k vertices, is introduced as a relaxation of clique. In this paper, we investigate the problem of enumerating all maximal k-plexes and present FaPlexen, an enumeration algorithm which integrates the “pivot” heuristic and new branching schemes. To our best knowledge, for the first time

APA, Harvard, Vancouver, ISO, and other styles

28

Ames, Brendan P. W., and Stephen A. Vavasis. "Convex optimization for the planted k-disjoint-clique problem." Mathematical Programming 143, no. 1-2 (2013): 299–337. http://dx.doi.org/10.1007/s10107-013-0733-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Wu, Jun, Chu-Min Li, Lu Jiang, Junping Zhou, and Minghao Yin. "Local search for diversified Top-k clique search problem." Computers & Operations Research 116 (April 2020): 104867. http://dx.doi.org/10.1016/j.cor.2019.104867.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Chang, Lijun, and Kai Yao. "Maximum k-Plex Computation: Theory and Practice." Proceedings of the ACM on Management of Data 2, no. 1 (2024): 1–26. http://dx.doi.org/10.1145/3639318.

Full text

Abstract:

The k-plex model relaxes the clique model by allowing each vertex to miss up to k neighbors, including the vertex itself. A 1-plex is a clique. Many exact algorithms have been recently designed for finding the k-plex with the largest number of vertices, known as the maximum k-plex computation problem. However, all the existing algorithms, except BS, has the trivial worst-case time complexity of O*(2n) when ignoring polynomial factors. On the other hand, although BS improves the time complexity to O*(βkn) where βk < 2 is a constant depending only on k, its practical performance is not satisf

APA, Harvard, Vancouver, ISO, and other styles

31

Gupta, Anupam, David G. Harris, Euiwoong Lee, and Jason Li. "Optimal Bounds for the k -cut Problem." Journal of the ACM 69, no. 1 (2022): 1–18. http://dx.doi.org/10.1145/3478018.

Full text

Abstract:

In the k -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger and Stein can solve this in roughly O ( n 2k ) time. However, lower bounds from conjectures about the k -clique problem imply that Ω ( n (1- o (1)) k ) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general k -cut in n 1.98k + O(1) time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights). In this work, we resolve the

APA, Harvard, Vancouver, ISO, and other styles

32

Teixeira, Rafael B., and Celina M. Herrera de Figueiredo. "The sandwich problem for cutsets: Clique cutset, k-star cutset." Discrete Applied Mathematics 154, no. 13 (2006): 1791–98. http://dx.doi.org/10.1016/j.dam.2006.03.023.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Konar, Aritra, and Nicholas D. Sidiropoulos. "Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 8 (2024): 8608–16. http://dx.doi.org/10.1609/aaai.v38i8.28705.

Full text

Abstract:

Dense subgraph discovery (DSD) is a key primitive in graph mining that typically deals with extracting cliques and near-cliques. In this paper, we revisit the optimal quasi-clique (OQC) formulation for DSD and establish that it is NP--hard. In addition, we reveal the hitherto unknown property that OQC can be used to explore the entire spectrum of densest subgraphs of all distinct sizes by appropriately varying a single hyperparameter, thereby forging an intimate link with the classic densest-k-subgraph problem (DkS). We corroborate these findings on real-world graphs by applying the simple gre

APA, Harvard, Vancouver, ISO, and other styles

34

YANG, GANG, ZHENG TANG, ZHIQIANG ZHANG, and YUNYI ZHU. "A FLEXIBLE ANNEALING CHAOTIC NEURAL NETWORK TO MAXIMUM CLIQUE PROBLEM." International Journal of Neural Systems 17, no. 03 (2007): 183–92. http://dx.doi.org/10.1142/s0129065707001056.

Full text

Abstract:

Based on the analysis and comparison of several annealing strategies, we present a flexible annealing chaotic neural network which has flexible controlling ability and quick convergence rate to optimization problem. The proposed network has rich and adjustable chaotic dynamics at the beginning, and then can converge quickly to stable states. We test the network on the maximum clique problem by some graphs of the DIMACS clique instances, p-random and k random graphs. The simulations show that the flexible annealing chaotic neural network can get satisfactory solutions at very little time and fe

APA, Harvard, Vancouver, ISO, and other styles

35

Gamarnik, D., A. Jagannath, and A. S. Wein. "Circuit Lower Bounds for the p-Spin Optimization Problem." Markov Processes And Related Fields, no. 2024 №1 (30) (May 27, 2024): 81–96. http://dx.doi.org/10.61102/1024-2953-mprf.2024.30.1.003.

Full text

Abstract:

We consider the problem of finding a near ground state of a p-spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent work [GJW20], we establish that any poly-size n-output circuit that produces a spin assignment with objective value within a certain constant factor of optimality, must have depth at least log n=(2 log log n) as n grows. This is stronger than the known state of the art bounds of the form (log n=(k(n) log log n)) for similar combinatorial optimization problems, where k(n) depends on the optimality value. For example, for

APA, Harvard, Vancouver, ISO, and other styles

36

Czumaj, Artur, and Christian Konrad. "Detecting cliques in CONGEST networks." Distributed Computing 33, no. 6 (2019): 533–43. http://dx.doi.org/10.1007/s00446-019-00368-w.

Full text

Abstract:

AbstractThe problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given graph H, the input network contains a subgraph isomorphic to H or not. We investigate this problem for H being a clique $$K_{\ell }$$ K ℓ in the classical distributed model, where the communication topology is the same as the topology of the underlying network, and with limited communication bandwidth on the links. Our first and main result is a lower bound, showing that detecting $$K_{\ell }$$ K ℓ requires $

APA, Harvard, Vancouver, ISO, and other styles

37

Bilò, Davide, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. "Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks." Proceedings of the AAAI Conference on Artificial Intelligence 39, no. 25 (2025): 26463–71. https://doi.org/10.1609/aaai.v39i25.34846.

Full text

Abstract:

We design sensitivity oracles for error-prone networks. For a network problem Π, the data structure preprocesses a network G=(V,E) and sensitivity parameter f such that, for any set F of up to f link or node failures, it can report the solution of Π in G-F. We study three network problems Π. - L-Hop Shortest Path: Given s,t in V, is there a shortest s-t-path in G-F with at most L links? - k-Path: Does G-F contain a simple path with k links? - k-Clique: Does G-F contain a clique of k nodes? Our main technical contribution is a new construction of (L,f)-replacement path coverings ((L,f)-RPC) in

APA, Harvard, Vancouver, ISO, and other styles

38

Liang, Zuosong, Erfang Shan, and Liying Kang. "The clique-transversal set problem in {claw, K 4 }-free planar graphs." Information Processing Letters 118 (February 2017): 64–68. http://dx.doi.org/10.1016/j.ipl.2016.10.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Li, Changhong. "Multi-objective Optimization Overlapping Community Detection Algorithm based on Subgraph Structure." Frontiers in Computing and Intelligent Systems 3, no. 3 (2023): 110–12. http://dx.doi.org/10.54097/fcis.v3i3.8580.

Full text

Abstract:

Community detection in complex networks has increasingly become an important topic in the network, but in most community detection methods, a single node only belongs to one community. In fact, there is often overlap among real-world online communities. In this paper, an overlapping community detection algorithm based on subgraph structure and multi-optimization method is designed. In this algorithm, the maximum clique mined by k-core decomposition is used as the clique node, thus the overlap characteristic is transformed into the inherent characteristic of the new graph. After that, a populat

APA, Harvard, Vancouver, ISO, and other styles

40

Gao, Jian, Zhenghang Xu, Ruizhi Li, and Minghao Yin. "An Exact Algorithm with New Upper Bounds for the Maximum k-Defective Clique Problem in Massive Sparse Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (2022): 10174–83. http://dx.doi.org/10.1609/aaai.v36i9.21257.

Full text

Abstract:

The Maximum k-Defective Clique Problem (MDCP), as a clique relaxation model, has been used to solve various problems. Because it is a hard computational task, previous works can hardly solve the MDCP for massive sparse graphs derived from real-world applications. In this work, we propose a novel branch-and-bound algorithm to solve the MDCP based on several new techniques. First, we propose two new upper bounds of the MDCP as well as corresponding reduction rules to remove redundant vertices and edges. The proposed reduction rules are particularly useful for massive graphs. Second, we present a

APA, Harvard, Vancouver, ISO, and other styles

41

Wang, Zhaocai, Zuwen Ji, Lei Li, and Dongmei Huang. "A Parallel Computational Algorithm for Solving the Maximum k-Vertex Weighted Clique Problem." Journal of Computational and Theoretical Nanoscience 12, no. 12 (2015): 6002–5. http://dx.doi.org/10.1166/jctn.2015.4749.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

BOUAJJANI, AHMED, and AGATHE MERCERON. "Parametric Verification of a Group Membership Algorithm." Theory and Practice of Logic Programming 6, no. 3 (2006): 321–53. http://dx.doi.org/10.1017/s1471068406002663.

Full text

Abstract:

We address the problem of verifying clique avoidance in the TTP protocol. TTP allows several stations embedded in a car to communicate. It has many mechanisms to ensure robustness to faults. In particular, it has an algorithm that allows a station to recognize itself as faulty and leave the communication. This algorithm must satisfy the crucial ‘non-clique’ property: it is impossible to have two or more disjoint groups of stations communicating exclusively with stations in their own group. In this paper, we propose an automatic verification method for an arbitrary number of stations $N$ and a

APA, Harvard, Vancouver, ISO, and other styles

43

PIKHURKO, OLEG, KATHERINE STADEN, and ZELEALEM B. YILMA. "The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques." Mathematical Proceedings of the Cambridge Philosophical Society 163, no. 2 (2017): 341–56. http://dx.doi.org/10.1017/s0305004116001031.

Full text

Abstract:

AbstractLet k := (k1,. . .,ks) be a sequence of natural numbers. For a graph G, let F(G;k) denote the number of colourings of the edges of G with colours 1,. . .,s such that, for every c ∈ {1,. . .,s}, the edges of colour c contain no clique of order kc. Write F(n;k) to denote the maximum of F(G;k) over all graphs G on n vertices. This problem was first considered by Erdős and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases.We prove that, for every k and n, there is a complete multipartite graph G on n vertices with F(G;k) = F(n;k). Also, for every

APA, Harvard, Vancouver, ISO, and other styles

44

Angelini, Patrizio, Peter Eades, Seok-Hee Hong, et al. "Graph Planarity by Replacing Cliques with Paths." Algorithms 13, no. 8 (2020): 194. http://dx.doi.org/10.3390/a13080194.

Full text

Abstract:

This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, we prove that h-Clique2Path Planarity is NP-complete even when h=4 and G is a simple 3-plane graph,

APA, Harvard, Vancouver, ISO, and other styles

45

Lai, Wenxing. "The Inapproximability of k-DominatingSet for Parameterized AC 0 Circuits †." Algorithms 12, no. 11 (2019): 230. http://dx.doi.org/10.3390/a12110230.

Full text

Abstract:

Chen and Flum showed that any FPT-approximation of the k-Clique problem is not in para- AC 0 and the k-DominatingSet (k-DomSet) problem could not be computed by para- AC 0 circuits. It is natural to ask whether the f ( k ) -approximation of the k-DomSet problem is in para- AC 0 for some computable function f. Very recently it was proved that assuming W [ 1 ] ≠ FPT , the k-DomSet problem cannot be f ( k ) -approximated by FPT algorithms for any computable function f by S., Laekhanukit and Manurangsi and Lin, seperately. We observe that the constructions used in Lin’s work can be carried out usi

APA, Harvard, Vancouver, ISO, and other styles

46

SALEH, SAGVAN ALI, and MHAND HIFI. "A FAST METHOD FOR OPTIMIZING THE K-CLUSTERING BI-CLIQUE COMPLETION PROBLEM IN TELECOMMUNICATION." Journal of The University of Duhok 20, no. 1 (2017): 175–83. http://dx.doi.org/10.26682/sjuod.2017.20.1.16.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Wu, Kuixian, Jian Gao, Rong Chen, and Xianji Cui. "Vertex Selection Heuristics in Branch-and-Bound Algorithms for the Maximum k-Plex Problem." International Journal on Artificial Intelligence Tools 28, no. 05 (2019): 1950015. http://dx.doi.org/10.1142/s0218213019500155.

Full text

Abstract:

As a relaxation of clique in graph theory, k-plex is a powerful tool for analyzing social networks and identifying cohesive structures in graphs. Recently, more and more researchers have concentrated on the algorithms for the maximum k-plex problem. Among those algorithms, a branch-and-bound algorithm proposed very recently shows a good performance on solving large sparse graphs, but does not work well on social networks. In this paper, we propose two novel vertex selection heuristic strategies for branching. The first one employs historical information of vertex reduction, and the second one

APA, Harvard, Vancouver, ISO, and other styles

48

Chen, Jiejiang, Yiyuan Wang, Shaowei Cai, Minghao Yin, Yupeng Zhou, and Jieyu Wu. "NukCP: An Improved Local Search Algorithm for Maximum k-Club Problem." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (2022): 10146–55. http://dx.doi.org/10.1609/aaai.v36i9.21254.

Full text

Abstract:

The maximum k-club problem (MkCP) is an important clique relaxation problem with wide applications. Previous MkCP algorithms only work on small-scale instances and are not applicable for large-scale instances. For solving instances with different scales, this paper develops an efficient local search algorithm named NukCP for the MkCP which mainly includes two novel ideas. First, we propose a dynamic reduction strategy, which makes a good balance between the time efficiency and the precision effectiveness of the upper bound calculation. Second, a stratified threshold configuration checking stra

APA, Harvard, Vancouver, ISO, and other styles

49

Fomin, Fedor V., and Petr A. Golovach. "Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs." Algorithmica 83, no. 7 (2021): 2170–214. http://dx.doi.org/10.1007/s00453-021-00822-x.

Full text

Abstract:

AbstractWe study algorithmic properties of the graph class $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e . More precisely, we identify a large class of optimization problems on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e solvable in time $$2^{{\mathcal{

APA, Harvard, Vancouver, ISO, and other styles

50

Fang, Zhiwen, Chu-Min Li, and Ke Xu. "An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem." Journal of Artificial Intelligence Research 55 (March 31, 2016): 799–833. http://dx.doi.org/10.1613/jair.4953.

Full text

Abstract:

Recently, MaxSAT reasoning is shown very effective in computing a tight upper bound for a Maximum Clique (MC) of a (unweighted) graph. In this paper, we apply MaxSAT reasoning to compute a tight upper bound for a Maximum Weight Clique (MWC) of a wighted graph. We first study three usual encodings of MWC into weighted partial MaxSAT dealing with hard clauses, which must be satisfied in all solutions, and soft clauses, which are weighted and can be falsified. The drawbacks of these encodings motivate us to propose an encoding of MWC into a special weighted partial MaxSAT formalism, called LW (Li

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!