Search

This paper presents a comprehensive survey of knowledge graphs in education. It covers the patterns and prospects of research in this area. A total of 48 relevant publications between 2011 and 2023 were collected from the Web of Science, Scopus, and ProQuest for review. The findings reveal a sharp increase in recent years in the body of research into educational knowledge graphs which was mainly conducted from institutions in China. Most of the relevant research work adopted a quantitative method, such as performance evaluation, user surveys, and controlled experiments, to assess the effectiveness of knowledge graph approaches. The findings also suggest that knowledge graph approaches were primarily researched and implemented in higher education institutions, with a focus on computer science, mathematics, and engineering. The most frequently addressed objectives included enhancing knowledge representation and providing personal learning recommendations, and the most common applications were concept instruction and educational recommendations. Diverse data resources, such as course materials, student learning behaviours, and online encyclopaedia, were processed to implement knowledge graph approaches in different scenarios. Relevant technical means employed for the implementation of knowledge graphs dealt with the purposes of building knowledge ontology, achieving recommendations, and creating knowledge graphs. Various pedagogies such as personalised learning and collaborative learning are supported by the knowledge graph approaches. The findings also identified key limitations in the relevant work, including insufficient information for knowledge graph construction, difficulty in extending applications across subject areas, the restricted scale and scope of data resources, and the lack of comprehensive user feedback and evaluation processes. [ABSTRACT FROM AUTHOR]

Graphs are used to solve many problems in mathematics and computer sciences. Many structures can be displayed with the help of graphs. For example, a directed graph can be used to show how websites are related to each other. Vague graph (VG) is one of the most important graphs in the fuzzy graph (FG)-theory, which can play a significant role in finding the most suitable places in construction and also finding the shortest path in computer networks. Connectivity indices are one of the most widely used topics in graph theory, which are used in other sciences, including computer science and chemistry. One of the most famous indices in the graph is the Wiener index, which belongs to the description of the molecular structure, which is used to design molecules with desirable properties. Therefore, in this paper, we introduce important topological indices such as Wiener index, Wiener absolute index, Randic index, Zegreb index, Harmonic index, and Average Wiener index on VGs and investigate their properties with several examples. Finally, an application of the Wiener index is given to find the most suitable place to build an university. [ABSTRACT FROM AUTHOR]

Let d-claw (or d-star) stand for K 1 , d , the complete bipartite graph with 1 and d ≥ 1 vertices on each part. The d-claw vertex deletion problem, d -claw-vd, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1 -claw-vd and 2 -claw-vd are just the famous vertex cover problem and the cluster vertex deletion problem, respectively. In this paper, we strengthen a hardness result recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d ≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 2020), we show that, for every d ≥ 3 , d -claw-vd is NP -complete even when restricted to split graphs without (d + 1) -claws, and split graphs of diameter 2. On the positive side, we prove that d -claw-vd is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in Cao et al (Theor Comput Sci, 2018) for 2 -claw-vd on block graphs to d -claw-vd for all d ≥ 2 and improves the polynomial-time algorithm proposed by Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs. [ABSTRACT FROM AUTHOR]

Graphs are used to solve many problems in mathematics and computer sciences. Many structures can be displayed with the help of graphs. For example, a directed graph can be used to show how websites are related to cach other. Vague graph (VG) is one of the most important graphs in the fuzzy graph (FG)-theory, which can play a significant role in finding the most suitable places in construction and also finding the shortest path in computer networks. Connectivity indices are one of the most widely used topics in graph theory, which are used in other sciences, including computer science and chemistry. One of the most famous indices in the graph is the Wiener index, which belongs to the description of the molecular structure, which is used to design molecules with desirable properties. Therefore, in this paper, we introduce important topological indices such as Wiener index, Wiener absolute index, Randic index, Zegreb index, Harmonic index, and Average Wiener index on VGs and investigate their properties with several examples. Finally, an application of the Wiener index is given to find the most suitable place to build an university. [ABSTRACT FROM AUTHOR]

Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). extended the classical +2 (respectively, +4) spanners for unweighted graphs of size O (n 3 / 2) (resp., O (n 7 / 5) ) to the weighted setting, where the additive error is + 2 W (resp., + 4 W ). This means that for every pair u, v, the additive stretch is at most + 2 W u , v , where W u , v is the maximal edge weight on the shortest u - v path (weights are normalized so that the minimum edge weight is 1). In addition, as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). showed a randomized algorithm yielding a + 8 W max spanner of size O (n 4 / 3) , here W max is the maximum edge weight in the entire graph. In this work we improve the latter result by devising a simple deterministic algorithm for a + (6 + ε) W spanner for weighted graphs with size O (n 4 / 3) (for any constant ε > 0 ), thus nearly matching the classical +6 spanner of size O (n 4 / 3) for unweighted graphs. Furthermore, we show a + (2 + ε) W subsetwise spanner of size O (n · | S |) , improving the + 4 W max result of as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). (that had the same size). We also show a simple randomized algorithm for a + 4 W emulator of size O ~ (n 4 / 3) . In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. It was proved by Abboud A, Bodwin G (J ACM 64(4):28–12820 2017) that such spanners must suffer polynomially large stretches. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size + O ~ (n · W) spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of Dor D et al. (SIAM J Comput 29:1740–1759, 2000) for unweighted graphs, we devise an efficient randomized algorithm producing a + 2 W spanner for weighted graphs of size O ~ (n 3 / 2) in O ~ (n 2) time. [ABSTRACT FROM AUTHOR]

In this paper we consider coloring problems on graphs and other combinatorial structures on standard Borel spaces. Our goal is to obtain sufficient conditions under which such colorings can be made well-behaved in the sense of topology or measure. To this end, we show that such well-behaved colorings can be produced using certain powerful techniques from finite combinatorics and computer science. First, we prove that efficient distributed coloring algorithms (on finite graphs) yield well-behaved colorings of Borel graphs of bounded degree; roughly speaking, deterministic algorithms produce Borel colorings, while randomized algorithms give measurable and Baire-measurable colorings. Second, we establish measurable and Baire-measurable versions of the Symmetric Lovász Local Lemma (under the assumption p (d + 1) 8 ⩽ 2 − 15 , which is stronger than the standard LLL assumption p (d + 1) ⩽ e − 1 but still sufficient for many applications). From these general results, we derive a number of consequences in descriptive combinatorics and ergodic theory. [ABSTRACT FROM AUTHOR]

Covering a graph with cohesive subgraphs is a classical problem in theoretical computer science, for example when the cohesive subgraph model considered is a clique. In this paper, we consider as a model of cohesive subgraph the 2-clubs, which are induced subgraphs of diameter at most 2. We prove new complexity results on the Min 2 - Club Cover problem, a variant recently introduced in the literature which asks to cover the vertices of a graph with a minimum number of 2-clubs. First, we answer an open question on the decision version of Min 2 - Club Cover that asks if it is possible to cover a graph with at most two 2-clubs, and we prove that it is W[1]-hard when parameterized by the distance to a 2-club. Then, we consider the complexity of Min 2 - Club Cover on some graph classes. We prove that Min 2 - Club Cover remains NP-hard on subcubic planar graphs, W[2]-hard on bipartite graphs when parameterized by the number of 2-clubs in a solution, and fixed-parameter tractable on graphs having bounded treewidth. [ABSTRACT FROM AUTHOR]

Graphs are useful for analysing the structure models in computer science, operations research, and sociology. The word metric dimension is the basis of the distance function, which has a symmetric property. Moreover, finding the resolving set of a graph is NP-complete, and the possibilities of finding the resolving set are reduced due to the symmetric behaviour of the graph. In this paper, we introduce the idea of the edge-multiset dimension of graphs. A representation of an edge is defined as the multiset of distances between it and the vertices of a set, B ⊆ V (Γ) . If the representation of two different edges is unequal, then B is an edge-multiset resolving a set of Γ. The least possible cardinality of the edge-multiset resolving a set is referred to as the edge-multiset dimension of Γ. This article presents preliminary results, special conditions, and bounds on the edge-multiset dimension of certain graphs. This research provides new insights into structure models in computer science, operations research, and sociology. They could have implications for developing computer algorithms, aircraft scheduling, and species movement between regions. [ABSTRACT FROM AUTHOR]

The cloud computing networks used in the IoT, and other themes of network architectures, can be investigated and improved by cheminformatics, which is a combination of chemistry, computer science, and mathematics. Cheminformatics involves graph theory and its tools. Any number that can be uniquely calculated by a graph is known as a graph invariant. In graph theory, networks are converted into graphs with workstations or routers or nodes as vertex and paths, or connections as edges. Many topological indices have been developed for the determination of the physical properties of networks involved in cloud computing. The study computed newly prepared topological invariants, K-Banhatti Sombor invariants (KBSO), Dharwad invariants, Quadratic-Contraharmonic invariants (QCI), and their reduced forms with other forms of cloud computing networks. These are used to explore and enhance their characteristics, such as scalability, efficiency, higher throughput, reduced latency, and best-fit topology. These attributes depend on the topology of the cloud, where different nodes, paths, and clouds are to be attached to achieve the best of the attributes mentioned before. The study only deals with a single parameter, which is a topology of the cloud network. The improvement of the topology improves the other characteristics as well, which is the main objective of this study. Its prime objective is to develop formulas so that it can check the topology and performance of certain cloud networks without doing or performing experiments, and also before developing them. The calculated results are valuable and helpful in understanding the deep physical behavior of the cloud's networks. These results will also be useful for researchers to understand how these networks can be constructed and improved with different physical characteristics for enhanced versions. [ABSTRACT FROM AUTHOR]

Highly efficient algorithms for solving the time constrained shortest path problem have been highlighted over the past decades to reduce the cost of vehicle travel in the road network. The paper presents a novel graph algorithm comprising three stages to acquire a time constrained shortest path between any two nodes on the map. In the first stage, the undirected graph is transformed into a directed graph (DT graph) by deleting edges that must not be included in any of the time constrained shortest paths. A variant DT tree with the destination as the root and the source as the leaf is then constructed from the DT graph in the second stage. By finding the minimal difference value between leaves and the root of the variant DT tree, we can eventually obtain a time constrained shortest path from the variant DT tree in the third stage. Experimental results show that our algorithm not only requires less running time than some classical graph algorithms but also can work immediately in the first stage without knowing the information of both the destination and a specific time constraint. [ABSTRACT FROM AUTHOR]

Graph theory is a powerful and essential tool for applied scientists and engineers in analyzing and designing algorithms for several problems. Graph theory has a vital role in complex systems, especially in computer sciences. Applications of graph theory can be found in many scientific disciplines such as operational research, engineering, life sciences, management sciences, coding, and computer science. In the literature, there are two algorithms for constructing decompositions for the circulant graphs C 2 r , r with 2 r vertices and r degree. For r , m ⩾ 2 , a circulant-balanced complete multipartite graph C mr , (m - 1) r is a generalization to C 2 r , r. Here, the major contributions are the generalization of the algorithms used for constructing the decompositions for the circulant graphs C 2 r , r to generalized algorithms that can be used for the decomposition of C mr , (m - 1) r that have mr vertices and (m - 1) r degree. These generalized algorithms manage us to decompose the circulant graphs C mr , (m - 1) r by different graph classes. The paper's novelty is demonstrated by the fact that it is the first to suggest general approaches for decomposing circulant-balanced complete multipartite graphs. The constructed results in the present paper are suitable for generating different codes and also have great importance in the design of experiments. [ABSTRACT FROM AUTHOR]

A graph structure is a useful tool in solving the combinatorial problems in different areas of computer science and computational intelligence systems. In this paper, we introduce the concept of cubic soft graph, complete cubic soft graph, (internal, external) cubic soft graphs and investigate some of their properties. Then we deal with fundamental operations, union, intersection, Cartesian product, composition of cubic soft graphs and illustrate these notions by several examples. We prove that cubic soft graphs under these operations are also a cubic soft graph. Finally, we describe an application of cubic soft graphs in decision making. [ABSTRACT FROM AUTHOR]

Continuous and discrete models as well as algorithms Bressan (2007) and Finbow and MacGillivray (2009) for firefighting problems are well-studied in Theoretical Computer Science. We introduce a new, discrete, and more general framework based on a graph to study firefighting problems in various terrains. In the context of this model, we present two different firefighting problems called village protection problems, where the goal is to protect a specific set of locations and provide efficient polynomial time algorithms for their solutions. We also discuss extensions of the model. [ABSTRACT FROM AUTHOR]

In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. "Classroom" is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part paper consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. In this third part of the three-part survey paper, we present a set of techniques to prove lower bounds for dynamic graph problems. In the first part1 of the survey, we presented the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part2 of the survey, we presented a set of techniques to prove upper bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Research in dynamic graphs has succeeded in obtaining efficient upper bounds for an extensive collection of problems. However, there are problems of stubborn nature. Such complex problems lead to the investigation of lower bounds. [ABSTRACT FROM AUTHOR]

In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. "Classroom" is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part article consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. This article presents the second part of the survey consisting of a set of techniques to prove upper bounds for dynamic graph problems. In the first part of the survey, we presented motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of upper bound results for their dynamic graph counterparts. The upper bound techniques used in dynamic graphs need attention from an implementation perspective, along with theoretical advances. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey. [ABSTRACT FROM AUTHOR]

In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. "Classroom" is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part article comprising a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. This article presents the first part of the survey outlining the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part of the survey, we will present a set of techniques to prove upper bounds for dynamic graph problems. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of lower bounds and upper bounds results for their dynamic graph counterparts. Along with theoretical advances, the techniques used in dynamic graphs need attention from an implementation perspective. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey. The survey can also be used to understand the first algorithms for several recent dynamic graph algorithms. [ABSTRACT FROM AUTHOR]

A graph structure is a generalization of simple graphs. Graph structures are very useful tools for the study of different domains of computational intelligence and computer science. A vague graph structure is a generalization of a vague graph. In this research paper, we present several different types of operations including cartesian product, cross product, lexicographic product, union, and composition on vague graph structures. We also introduce some results of operations. [ABSTRACT FROM AUTHOR]

The group nearest neighbor (GNN) search on a road network $G_r$ G r , i.e., finding the spatial objects as activity assembly points with the smallest sum of distances to query users on $G_r$ G r , has been extensively studied; however, previous works neglected the fact that social relationships among query users, which ensure the maximally favorable atmosphere in the activity, can play an important role in GNN queries. Meanwhile, the ratings of spatial objects can also be used as recommended guidelines. Many real-world applications, such as location-based social networking services, require such queries. In this paper, we study two new problems: (1) a GNN search on a road network that incorporates cohesive social relationships (CGNN) and (2) a CGNN query under multi-criteria (MCGNN). Specifically, both the query users of highest closeness and the corresponding top- $j$ j objects are retrieved. To address critical challenges on the effectiveness of results and the efficiency of computation over large road-social networks: (1) for CGNN, we propose a filtering-and-verification framework. During filtering, we prune substantial unpromising users and objects using social and geospatial constraints. During verification, we obtain the object candidates, among which the top $j$ j are selected, with respect to the qualified users; (2) for MCGNN, we propose threshold-based selection and expansion strategies, where different strict boundaries are proposed to ensure that correct top- $j$ j objects are found early. Moreover, we further optimize search strategies to improve query performance. Finally, experimental results on real social and road networks significantly demonstrate the efficiency and efficacy of our solutions. [ABSTRACT FROM AUTHOR]

Recent work has shown that entity resolution (ER) can be effectively performed by gradual machine learning (GML). GML begins with some automatically labeled easy instances and, then, gradually labels more challenging instances by iterative factor graph inference without human intervention. In GML, shared features serve as the medium for knowledge conveyance between easy instances and more challenging ones. The existing GML solution supposes that features play independent roles in gradual inference. However, in real scenarios, this assumption may be untenable since features are usually correlated with each other. To address this limitation, this article proposes an attention-enhanced approach to improve the accuracy of gradual inference. We first propose a method of spectral feature representation to map correlated features to close points in the same vector space and, then, present a model of attention neural network to learn the decisive features, given arbitrary combinations of features for improved feature weighting. Finally, our extensive experiments on real benchmark data have validated the efficacy of the proposed approach. [ABSTRACT FROM AUTHOR]

Developing efficient graph algorithms implementations is an extremely important problem of modern computer science, since graphs are frequently used in various real-world applications. Graph algorithms typically belong to the data-intensive class, and thus using architectures with high-bandwidth memory potentially allows to solve many graph problems significantly faster compared to modern multicore CPUs. Among other supercomputer architectures, vector systems, such as the SX family of NEC vector supercomputers, are equipped with high-bandwidth memory. However, the highly irregular structure of many real-world graphs makes it extremely challenging to implement graph algorithms on vector systems, since these implementations are usually bulky and complicated, and a deep understanding of vector architectures hardware features is required. This paper presents the world first attempt to develop an efficient and simultaneously simple graph processing framework for modern vector systems. Our vector graph library (VGL) framework targets NEC SX-Aurora TSUBASA as a primary vector architecture and provides relatively simple computational and data abstractions. These abstractions incorporate many vector-oriented optimization strategies into a high-level programming model, allowing quick implementation of new graph algorithms with a small amount of code and minimal knowledge about features of vector systems. In this paper, we evaluate the VGL performance on four widely used graph processing problems: breadth-first search, single source shortest paths, connected components, and page rank. The provided comparative performance analysis demonstrates that the VGL-based implementations achieve significant acceleration over the existing high-performance frameworks and libraries: up to 14 times speedup over multicore CPUs (Ligra, Galois, GAPBS) and up to 3 times speedup compared to NVIDIA GPU (Gunrock, NVGRAPH) implementations. [ABSTRACT FROM AUTHOR]

Novel road-network applications often recommend a moving object (e.g., a vehicle) about interesting services or tasks on its way to a destination. A taxi-sharing system, for instance, suggests a new passenger to a taxi while it is serving another one. The traveling cost is then shared among these passengers. A fundamental query is: given two nodes $s$ s and $t$ t , and an area $\mathcal {A}$ A on road network graph $\mathcal {G}$ G , is there a “good” route (e.g., short enough path) $P$ P from $s$ s to $t$ t that crosses $\mathcal {A}$ A in $\mathcal {G}$ G ? In a taxi-sharing system, $s$ s and $t$ t can be a taxi's current and destined locations, and $\mathcal {A}$ A contains all the places to which a person waiting for a taxi is willing to walk. Answering this Route and Area Matching (ROAM) Query allows the application involved to recommend appropriate services to users efficiently. In this paper, we examine efficient ROAM query algorithms. Particularly, we develop solutions for finding a $\rho$ ρ -route, which is an $s$ s - $t$ t path that passes $\mathcal {A}$ A , with a length of at most $(1+\rho)$ (1 + ρ) times the shortest distance between $s$ s and $t$ t . The existence of a $\rho$ ρ -route implies that a service or task located at $\mathcal {A}$ A can be found for a given moving object $m$ m , and that $m$ m only deviates slightly from its current route. We present comprehensive studies on index-free and index-based algorithms for answering ROAM queries. Comprehensive experiments show that our algorithm runs up to 30 times faster than baseline algorithms. [ABSTRACT FROM AUTHOR]

The main scope of our study is to analyse the sociological and psychological resources of the pedagogical communication employed at the level of didactic message, exploited from the perspective of computer science approached as a model of applied philosophy. The structure of the didactic message is pedagogically fixed at the level of the correlation between student acquired knowledge and his positive formation. From the computer science perspective, it is necessary to analyse the sociological (cultural) and psychological (cognitive and noncognitive) resources of the information. This information included in the school programs, must be related to the competences that include in their structure three categories, defined in terms of knowledge: theoretical, applied, conditional. The transformation of knowledge into special informatic resources, with a positive formative value, requires their transforming within an ascending informatic process. It involves the following actions: a) transformation of data into information; b) assembling information at the database level, by creating and using algorithms and graphs; c) correlation of information integrated into the database at the network level, applicable in open contexts; d) continuous improvement of the results under conditions of external inverse connection (realized by the educator, the teacher) and internal (realized by the educated, the student). [ABSTRACT FROM AUTHOR]

Social network analysis has become an important topic for researchers in sociology and computer science. Similarities among individuals form communities as the basic constitutions of social networks. Regarding the importance of communities, community detection is a fundamental step in the study of social networks typically modeled as large-scale graphs. Detecting communities in such large-scale graphs which generally suffers from the curse of dimensionality is the main objective followed in this study. An efficient modularity-based community detection algorithm called MDPCluster is introduced in order to detect communities in large-scale graphs in a timely manner. To address the high dimensionality problem, first, a Louvain-based algorithm is utilized by MDPCluster to distinguish initial communities as super-nodes and then a Modified Discrete Particle Swarm Optimization algorithm, called MDPSO is leveraged to detect communities through maximizing modularity measure. MDPSO discretizes Particle Swarm Optimization using the idea of transmission tendency and also escapes from premature convergence thereby a mutation operator inspired by Genetic Algorithm. To evaluate the proposed method, six standard datasets, i.e., American College Football, Books about US Politics, Amazon Product Co-purchasing, DBLP, GR-QC and HEP-TH have been employed. The first two are known as synthetic datasets whereas the rest are real-world datasets. In comparison to eight state-of-the-art algorithms, i.e., Stationary Genetic Algorithm, Generational Genetic Algorithm, Simulated Annealing-Stationary Genetic Algorithm, Simulated Annealing-Generational Genetic Algorithm, Grivan–Newman, Danon and Label Propagation Algorithm, the results indicate the superiorities of MDCluster in terms of modularity, Normalized Mutual Information and execution time as well. [ABSTRACT FROM AUTHOR]

We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm's past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of (2 + ε) and an amortized update time of O (log n / ε 2) . Our result can be generalized to give a fully dynamic O (f 3) -approximate algorithm with O (f 2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices. [ABSTRACT FROM AUTHOR]

Graph matching is a fundamental problem in theoretical computer science and artificial intelligence, and lays the foundation for many computer vision and machine learning tasks. Approximate algorithms are necessary for graph matching due to its NP-complete nature. Inspired by the usage in network-related tasks, random walk is generalized to graph matching as a type of approximate algorithm. However, it may be inappropriate for the previous random walk-based graph matching algorithms to utilize continuous techniques without considering the discrete property. In this paper, we propose a novel random walk-based graph matching algorithm by incorporating both continuous and discrete constraints in the optimization process. Specifically, after interpreting graph matching by random walk, the continuous constraints are directly embedded in the random walk constraint in each iteration. Further, both the assignment matrix (vector) and the pairwise similarity measure between graphs are iteratively updated according the discrete constraints, which automatically leads the continuous solution to the discrete domain. Comparisons on both synthetic and real-world data demonstrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

One of the important non-linear data structures in Computer Science is graph. Most of the real life network, be it a road transportation network, or airlines network or a communication network etc., cannot be exactly transformed into a graph model, but into a Multigraphs model. The Multigraph is a topological generalization of the graph where multiple links (or edges/arcs) may exist between two nodes unlike in graph. The existing algorithms to extract the neutrosophic shortest path in a graph cannot be applied to a Multigraphs. In this paper a method is developed to extract the neutrosophic shortest path in a directed Multigraph and then the corresponding algorithm is designed. The classical Dijkstra's algorithm is applicable to graphs only where all the link weights are crisp, but we borrow this concept to apply to Multigraphs where the weights of the links are neutrosophic numbers (NNs). This new method may be useful in many application areas of computer science, communication networks, transportation networks, etc. in particular in those type of networks which cannot be modelled into graphs but into Multigraphs. [ABSTRACT FROM AUTHOR]

Let B = (X , Y , E) be a bipartite graph. A half-square of B has one color class of B as vertex set, say X; two vertices are adjacent whenever they have a common neighbor in Y. Every planar graph is a half-square of a planar bipartite graph, namely of its subdivision. Until recently, only half-squares of planar bipartite graphs, also known as map graphs (Chen et al., in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, STOC '98, pp 514–523. 10.1145/276698.276865, 1998; J ACM 49(2):127–138. 10.1145/506147.506148, 2002), have been investigated, and the most discussed problem is whether it is possible to recognize these graphs faster and simpler than Thorup's O (n 120) -time algorithm (Thorup, in: Proceedings of the 39th IEEE symposium on foundations of computer science (FOCS), pp 396–405. 10.1109/SFCS.1998.743490, 1998). In this paper, we identify the first hardness case, namely that deciding if a graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced bisplit graphs form a proper subclass of star convex bipartite graphs). For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we give good structural characterizations of their half-squares that imply efficient recognition algorithms. As a by-product, we obtain new characterizations of unit interval graphs, interval graphs, and of strongly chordal graphs in terms of half-squares of biconvex bipartite, convex bipartite, and of chordal bipartite graphs, respectively. Good characterizations of half-squares of star convex and star biconvex bipartite graphs are also given, giving linear-time recognition algorithms for these half-squares. [ABSTRACT FROM AUTHOR]

In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer r > 1 , and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of r for maximum independent set in O ∗ (exp (O ~ (n / r log 2 r + r log 2 r))) time, r for chromatic number in O ∗ (exp (O ~ (n / r log r + r log 2 r))) time, (2 - 1 / r) for minimum vertex cover in O ∗ (exp (n / r Ω (r))) time, and (k - 1 / r) for minimum k-hypergraph vertex cover in O ∗ (exp (n / (k r) Ω (k r))) time. (Throughout, O ~ and O ∗ omit polyloglog (r) and factors polynomial in the input size, respectively.) The best known time bounds for all problems were O ∗ (2 n / r) (Bourgeois et al. in Discret Appl Math 159(17):1954–1970, 2011; Cygan et al. in Exponential-time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by exp (n 1 - o (1) / r 1 + o (1)) lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370–379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking O ∗ (2 n / r) bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan's PCP (Chan in J. ACM 63(3):27:1–27:32, 2016). It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture (Dinur in Electron Colloq Comput Complex (ECCC) 23:128, 2016; Manurangsi and Raghavendra in A birthday repetition theorem and complexity of approximating dense CSPs, 2016). [ABSTRACT FROM AUTHOR]

In the Subset Feedback Vertex Set (Subset-FVS) problem the input is a graph G on n vertices, a subset T of vertices of G called the "terminal" vertices, and an integer k. The task is to determine whether there exists a subset of vertices of cardinality at most k which together intersect all cycles which pass through the terminals. Subset-FVS generalizes several well studied problems including Feedback Vertex Set and Multiway Cut. This problem is known to be NP-Complete, even in split graphs. Cygan et al. (SIAM J Discrete Math 27(1):290–309, 2013) proved that Subset-FVS is fixed parameter tractable (FPT ) in general graphs when parameterized by k. In split graphs a simple observation reduces the problem to an equivalent instance of the 3-Hitting Set problem with the same solution size. This directly implies, for Subset-FVSrestricted to split graphs, (i) an FPT algorithm which solves the problem in O ⋆ (2. 076 k) time (The O ⋆ () notation hides polynomial factors.) (Wahlström in Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. Thesis, Department of Computer and Information Science, Linköpings universitet, 2007), and (ii) a kernel of size O (k 3) . We improve both these results for Subset-FVS on split graphs; we derive (i) a kernel of size O (k 2) which is the best possible unless NP ⊆ coNP / poly , and (ii) an algorithm which solves the problem in time O ∗ (2 k) . Our algorithm, in fact, solves Subset-FVS on the more general class of chordal graphs, also in O ∗ (2 k) time. To the best of our knowledge, the fastest known exact algorithm for Subset-FVS on chordal graphs is based on the 3-Hitting Set algorithm of Fomin et al. (JACM 66(2):8, 2019) which runs in O ∗ (1. 5182 n) time. Applying the results of Fomin et al. (2019) to our FPT algorithm yields two exact exponential-time algorithms for Subset-FVS on chordal graphs: a randomized algorithm which runs in O ∗ (1. 5 n) time, and a deterministic algorithm which runs in O ∗ ((1.5 + ε) n) time for any fixed ε > 0 . [ABSTRACT FROM AUTHOR]

Discovering triangles in large graphs is a well-studied area; however, both external-memory performance of existing methods and our understanding of the complexity involved leave much room for improvement. To shed light on this problem, we first generalize the existing in-memory algorithms into a single framework of 18 triangle-search techniques. We then develop a novel external-memory approach, which we call Pruned Companion Files (PCF), that supports operation of all 18 algorithms, while significantly reducing I/O compared to the common methods in this area. After finding the best node-traversal order, we build an implementation around it using SIMD instructions for list intersection and PCF for I/O. This method runs 5-10 times faster than the available implementations and exhibits orders of magnitude less I/O. In one of our graphs, the program finds 1 trillion triangles in 237 seconds using a desktop CPU. [ABSTRACT FROM AUTHOR]

We revisit a concept that has been central in some early stages of computer science, that of structured programming : a set of rules that an algorithm must follow in order to acquire a certain desirable structure. While much has been written about structured programming, an important issue has been left unanswered: given an arbitrary program, describe an algorithm to decide whether or not it is structured , that is, whether it conforms to the stated principles of structured programming. We refer to a classical concept of structured programming, as described by Dijkstra. By employing graph theoretic techniques, we formulate an efficient algorithm for answering this question. First, we introduce the class of graphs which correspond to structured programs, which we call Dijkstra Graphs. Then we present a greedy O (n) -time algorithm for recognizing such graphs. Furthermore, we describe an isomorphism algorithm for Dijkstra graphs, whose complexity is also linear in the number of vertices of the graph. [ABSTRACT FROM AUTHOR]

This document is a special section of the SIAM Journal on Computing, focusing on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018). It includes ten fully refereed papers that were presented at the symposium in Paris in October 2018. The papers cover a wide range of topics, including complexity theory, graph algorithms, approximation algorithms, cryptography, quantum computing, pseudorandom generators, matrix multiplication, and graph sparsification. The papers underwent an extensive refereeing process, and the authors and anonymous referees are thanked for their efforts. The special section was prepared with the help of the guest editors and the SIAM Publications Manager. [Extracted from the article]