Search

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we present a new degree-based estimator for the size of maximum matching in bounded arboricity graphs. When the arboricity of the graph is bounded by α , the estimator gives a α + 2 factor approximation of the matching size. For planar graphs, we show the estimator does better and returns a 3.5 approximation of the matching size. Using this estimator, we get new results for approximating the matching size of planar graphs in the streaming and distributed models of computation. In particular, in the vertex-arrival streams, we get a randomized O n ε 2 log n space algorithm for approximating the matching size of a planar graph on n vertices within (3.5 + ε) factor. Similarly, we get a simultaneous protocol in the vertex-partition model for approximating the matching size within (3.5 + ε) factor using O n 2 / 3 ε 2 log n communication from each player. In comparison with previous works, the estimator in this paper does not need to know the arboricity of the input graph and improves the approximation factor in the case of planar graphs. [ABSTRACT FROM AUTHOR]

In 2011, Liu, et al. investigated the structural controllability of directed networks. They proved that the minimum number of input signals, driver nodes, can be determined by seeking a maximum matching in the directed network. Thus, the algorithm for seeking a maximum matching is the key to solving the structural controllability problem of directed networks. In this study, the authors provide algebraic expressions for matchings and maximum matchings proposed by Liu, et al. (2011) via a new matrix product called semi-tensor product, based on which the corresponding algorithms are established to seek matchings and maximum matchings in digraphs, which make determining the number of driver nodes tractable in computer. In addition, according to the proposed algorithm, the authors also construct an algorithm to distinguish critical arcs, redundant arcs and ordinary arcs of the directed network, which plays an important role in studying the robust control problem. An example of a small network from Liu's paper is used for algorithm verification. [ABSTRACT FROM AUTHOR]

The role of this paper gives short notes about Konigsberg Bridge Problem. It is used to evaluate the process of calculating the Maximal Matching and Maximum Matching in the Graph of Konigsberg Bridge Problem. Here it analyzes the degree of the each vertex and the adjacency of the edges of the corresponding graph. It explains about the history of Konigsberg, the creation of Konigsberg Bridge Problem and the Euler Solution for Konigsberg Bridge Problem by the condition of traversable. Rules for traversable is also analyzed in this paper. It gives some idea to make the graph as traversable by the concept of Matching. It is used to find in which of the bridge is common used by the people at many times. [ABSTRACT FROM AUTHOR]

In a recent paper, Avis, Bremner, Tiwary and Watanabe gave a method for constructing linear programs (LPs) based on algorithms written in a simple programming language called Sparks. If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size and its optimum solution contains x as well as a complete execution trace of the algorithm. Their method led us to the construction of a compiler called sparktope which we describe in this paper. This compiler allows one to generate polynomial sized LPs for problems in P that have exponential extension complexity, such as matching problems in non-bipartite graphs. In this paper, we describe sparktope, the language Sparks, and the assembler instructions and LP constraints it produces. This is followed by two concrete examples, the makespan problem and the problem of testing if a matching in a graph is maximum, both of which are known to have exponential extension complexity. Computational results are given. In discussing these examples, we make use of visualization techniques included in sparktope that may be of independent interest. The extremely large linear programs produced by the compiler appear to be quite challenging to solve using currently available software. Since the optimum LP solutions can be computed independently they may be useful as benchmarks. Further enhancements of the compiler and its application are also discussed. [ABSTRACT FROM AUTHOR]

Let S be a subset of V(G). The vertices of S are colored black and the vertices of V (G) - S are colored white. The color-change-rule is defined as if there is a black vertex u having an unique white neighbor v, then change the color of v to black. The zero forcing number of a graph, denoted by Z(G), is the minimum cardinality of a set S such that all vertices of V(G) are black by repeating the color-change-rule, which was proposed at the AIM-minimum rank group in 2008 to bound the maximal nullity of G. Hence it has received much attention. Our interest is to study the zero forcing number of graphs with matching number α ′ (G) and cyclomatic number c(G). In the paper, utilizing the alternating path and an operation associated with a vertex partition, we verify the sharp bounds that n (G) - 2 α ′ (G) ≤ Z (G) ≤ n (G) - α ′ (G) + c (G) - 1 for n (G) ≥ 3 . The extremal graphs attain the upper bound are completely characterized. [ABSTRACT FROM AUTHOR]

In this paper, we study the enumeration of spanning trees and maximum matchings of the Fibonacci graphs. It is proved that the number of all spanning trees of a Fibonacci graph with n vertices is (2 n − 2) th Fibonacci number. We also obtained a formula for the number of maximum matchings of Fibonacci graphs in terms of Fibonacci numbers. [ABSTRACT FROM AUTHOR]

Distributed cooperative control of multi-agent systems is broadly applied in artificial intelligence in which time delay is of great concern because of its ubiquitous. This paper considers the controllability of leader-follower multi-agent systems with input and communication delays. For the first-order systems with input delay, neighbor-based protocol is adopted to realize the interactions among agents, yielding a system with delay existed in state and control input. New notions of interval controllability and interval structural controllability for the system are defined. Algebraic criterion is established for interval controllability, and graph-theoretic interpretation is put forward for the interval structural controllability. Results imply that input delay of the multi-agent systems has significant influence on the interval controllability and interval structural controllability. Corresponding conclusions are generalized to the first-order systems and the high-order ones with communication delays, respectively. Example is attached to illustrate the work. [ABSTRACT FROM AUTHOR]

A matching in a graph is a set of pairwise nonadjacent edges. A maximum matching is a matching which covers as many vertices as possible. In this paper, using the Gallai–Edmonds Structure Theorem, we obtain a characterization of graphs each of whose edges belongs to at most one maximum matching. [ABSTRACT FROM AUTHOR]

We investigate the problem to schedule a set of precedence constrained jobs of unit size on an open-shop or on a flow-shop to minimize the makespan. The precedence constraints among the jobs are presented as a directed acyclic graph called the precedence graph. When the number of machines in the shop is part of the input, both problems are strongly NP-hard on general precedence graphs, but were proven polynomial-time solvable for some special precedence graphs such as intrees. In this paper, we characterize improved lower bounds on the minimum makespan in terms of the number of agreeable pairings among certain jobs and propose approximation algorithms based on a maximum matching among these jobs, so that every agreeable pair of jobs can be processed on different machines simultaneously. For open-shop with an arbitrary precedence graph and for flow-shop with a spine precedence graph, both achieved approximation ratios are 2 -- m, where m is the number of machines in the shop. [ABSTRACT FROM AUTHOR]

The maximum matching problem is of great interest in many areas, for example, statistical physics and theoretical computer science. However, precise determining of maximum matchings in general graphs is a challenge and calculationally intractable. In this paper, we study analytically maximum matching problem in the pseudofractal scale-free web. We derive exact expressions for size and number of maximum matchings of the network based on self-similar structure and iterative construction of network, and obtain asymptotic incremental constant for the number of maximum matchings. The obtained results are helpful to understand the structural characteristics of scale-free networks with pseudofractality. [ABSTRACT FROM AUTHOR]

In many random assignment problems, the central planner pursues their own policy objective, such as matching size and minimum quota fulfillment. Several practically important policy objectives do not align with agents' preferences and are known to be incompatible with strategy-proofness. This paper demonstrates that such policy objectives can be attained using mechanisms that satisfy Bayesian incentive compatibility within a restricted domain of von Neumann Morgenstern utilities. We establish that a mechanism satisfies Bayesian incentive compatibility in an inverse-bounded-indifference domain if and only if the mechanism satisfies the three axioms of swap monotonicity, lower invariance, and interior upper variance. We apply this axiomatic characterization to analyze the incentive property of the constrained random serial dictatorship mechanism (CRSD). CRSD is designed to generate an individually rational assignment that optimizes the central planner's policy objective function. Since CRSD satisfies these axioms, it is Bayesian incentive compatible within an IBI domain. [ABSTRACT FROM AUTHOR]

In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results by Karp and Sipser suggest that the first algorithm is superior. In this paper we show that this is indeed the case, at least for random k‐regular graphs. We show that w.h.p. the first algorithm will find a matching of size n/2−O(logn) in a random k‐regular graph, k = O(1). We also show that the algorithm can be adapted to find a maximum matching in O(n) time w.h.p. This is to be compared with O(n3/2) time for the worst‐case. [ABSTRACT FROM AUTHOR]

Genomic Scaffold Filling problem forms an important class of problems, and has been paid lots of attention in the literature. In this paper, we study one of the Genomic Scaffold Filling problems, called One-sided-GSF-max-BC problem. In this paper, we give a new approximation algorithm for the problem. For any given instance of the One-sided-GSF-max-BC problem, auxiliary graphs are constructed based on the given instance and the relation between maximum matching in auxiliary graphs and optimal solution is studied, which results in an approximation algorithm with ratio 2.57. [ABSTRACT FROM AUTHOR]

For over a decade now we have been witnessing the success of massive parallel computation frameworks, such as MapReduce, Hadoop, Dryad, or Spark. Compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises however in this context is can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the maximum matching problem. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in O(log n) rounds. Lattanzi et al. [SPAA, ACM, New York, 2011, pp. 85--94] showed that if each machine has n1+\Omega (1) memory, this problem can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow-up work, seem though to get stuck in a fundamental way at roughly O(log n) rounds once we enter the (at most) near-linear memory regime. In this paper, we break the above O(log n) round complexity bound even in the case of slightly sublinear memory per machine. In fact, our improvement here is almost exponential: we are able to deliver a (1 + \epsilon)-approximate maximum matching for any fixed constant \epsilon > 0 in O((log log n)2) rounds. To establish our result we need to deviate from the previous work in two important ways. First, we use vertex-based graph partitioning, instead of the edge-based approaches that were utilized so far. Second, we develop a technique of round compression. [ABSTRACT FROM AUTHOR]

Nowadays, large cities face numerous problems caused by the rapidly increasing number of vehicles on road. Carpooling has been shown as an efficient solution to ease the traffic pressure. The objective of our carpool scheduling problem is to minimise the number of carpools needed to transport users. Previous research on the similar topic introduces static capacity constraint which limits the carpool size to the vehicle's capacity. However, it is unnecessary since a seat in the vehicle can be occupied by several passengers if their routes are not overlapped. In this paper, we remove this constraint, which allows a vehicle to serve more users than its capacity. We propose a greedy approach based on the iterative matching and merging. Specifically, starting from a set of single-user carpools, the algorithm iteratively checks the merge-ability between carpools, and then applies the maximum matching algorithm to maximise the number of carpools merged. In addition, two methods are proposed to reduce the time complexity of merge-ability checking process. Furthermore, we improve the time efficiency of our algorithms by exploiting geometry properties. Experimental results on synthetic and real-world datasets show that our algorithms have better performances than baseline. [ABSTRACT FROM AUTHOR]

A critical prerequisite for controlling complex networks is to find a driver node set with a structural controllability guarantee. This paper introduces the control capacity for a driver node set and solves the problem of finding a complete minimum driver node set that not only guarantees network structural controllability but achieves the desired level of control capacity. A novel algorithmic framework is proposed which is based on the concept of equivalent set and approximate matching replacement technique. The proposed algorithmic framework is shown to outperform the state-of-the-art approaches in the literature. The validity of the proposed algorithm is analyzed and the performance is evaluated by experiments on artificial and real-world complex networks. [ABSTRACT FROM AUTHOR]

In the partial degree bounded edge packing problem (PDBEP), the input is an undirected graph G=(V,E) with capacity cv∈N on each vertex v. The objective is to find a feasible subgraph G′=(V,E′) maximizing |E′|, where G′ is said to be feasible if for each e={u,v}∈E′, degG′(u)≤cu or degG′(v)≤cv. In the weighted version of the problem, additionally each edge e∈E has a weight w(e) and we want to find a feasible subgraph G′=(V,E′) maximizing ∑e∈E′w(e). The problem is already NP-hard if cv=1 for all v∈V (Zhang in: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14-16, pp 359-367, 2012). In this paper, we introduce a generalization of the PDBEP problem. We let the edges have weights as well as demands, and we present the first constant-factor approximation algorithms for this problem. Our results imply the first constant-factor approximation algorithm for the weighted PDBEP problem, improving the result of Aurora et al. (FAW-AAIM 2013) who presented an O(logn)-approximation for the weighted case. We also study the weighted PDBEP problem on hypergraphs and present a constant factor approximation if the maximum degree of the hypergraph is bounded above by a constant. We study a generalization of the weighted PDBEP problem with demands where each edge additionally specifies whether it requires at least one, or both its end-points to not exceed the capacity. The objective is to pick a maximum weight subset of edges. We give a constant factor approximation for this problem. We also present a PTAS for the weighted PDBEP problem with demands on H-minor free graphs, if the demands on the edges are bounded by polynomial. We show that the PDBEP problem is APX-hard even for bipartite graphs with cv=1,∀v∈V and having degree at most 3. [ABSTRACT FROM AUTHOR]

Uncertain graphs are employed to describe graph models with indeterministic information that produced by human beings. This paper aims to study the maximum matching problem in uncertain graphs. The number of edges of a maximum matching in a graph is called matching number of the graph. Due to the existence of uncertain edges, the matching number of an uncertain graph is essentially an uncertain variable. Different from that in a deterministic graph, it is more meaningful to investigate the uncertain measure that an uncertain graph is k-edge matching (i.e., the matching number is greater than or equal to k). We first study the properties of the matching number of an uncertain graph, and then give a fundamental formula for calculating the uncertain measure. We further prove that the fundamental formula can be transformed into a simplified form. What is more, a polynomial time algorithm to numerically calculate the uncertain measure is derived from the simplified form. Finally, some numerical examples are illustrated to show the application and efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph $$G= (A\, \dot{\cup }\, P, E)$$ with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between $$\textsf {NP}$$ -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $$u_{\max }$$ as basis, and we prove that this dependence is necessary unless $$\textsf {FPT}= \textsf {W}[1]$$ . The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee $$u_{\max }+1$$ , which is asymptotically best possible unless $$\textsf {P}= \textsf {NP}$$ . Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas. [ABSTRACT FROM AUTHOR]

In 1979, Nishizeki and Baybars showed that every planar graph with minimum degree 3 has a matching of size n3+c (where the constant c depends on the connectivity), and even better bounds hold for planar graphs with minimum degree 4 and 5. In this paper, we investigate similar matching‐bounds for 1‐planar graphs, that is, graphs that can be drawn such that every edge has at most one crossing. We show that every 1‐planar graph with minimum degree 3 has a matching of size at least 17n+127, and this is tight for some graphs. We provide similar bounds for 1‐planar graphs with minimum degree 4 and 5, while the case of minimum degree 6 and 7 remains open. [ABSTRACT FROM AUTHOR]

Let D be a digraph and let α (D) , α ′ (D) and λ (D) be independence number, the matching number and the arc-strong connectivity of D , respectively. Bang-Jensen and Thommassé in 2011 conjectured that every digraph D with λ (D) ≥ α (D) is supereulerian. In [J. Graph Theory, 81(4), (2016) 393-402], it is shown that every digraph D with λ (D) ≥ α ′ (D) is supereulerian. In this paper, we introduced the symmetric core of a digraph and use it to show that each of the following holds for a strong digraph D on n ≥ 3 vertices with λ (D) ≥ α ′ (D) − 1. (i) There exists a family D (n) of well-characterized digraphs such that for any digraph D with α ′ (D) ≤ 2 , D has a spanning trial if and only if D is not a member in D (n). (i i) If α ′ (D) ≥ 3 , then D has a spanning trail. (i i i) If α ′ (D) ≥ 3 and n ≥ 2 α ′ (D) + 3 , then D is supereulerian. (i v) If λ (D) ≥ α ′ (D) ≥ 4 and n ≥ 2 α ′ (D) + 3 , then for any pair of vertices u and v of D , D contains a spanning (u , v) -trail. [ABSTRACT FROM AUTHOR]

Copyright of SCIENCE CHINA Information Sciences is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

A connected graph $$G$$ is said to be factor-critical if $$G-v$$ has a perfect matching for every vertex $$v$$ of $$G$$ . Lovász proved that every factor-critical graph has an ear decomposition. In this paper, the ear decomposition of the factor-critical graphs $$G$$ satisfying that $$G-v$$ has a unique perfect matching for any vertex $$v$$ of $$G$$ with degree at least 3 is characterized. From this, the number of maximum matchings of factor-critical graphs with the special ear decomposition is obtained. [ABSTRACT FROM AUTHOR]

For a graph $$G$$ let $$\alpha (G)$$ and $$\mu (G)$$ denote respectively the cardinality of a maximum stable set and of a maximum matching of $$G$$ . It is well-known that computing $$\alpha (G)$$ is NP-hard and that computing $$\mu (G)$$ can be done in polynomial time. In particular checking if $$\alpha (G)=\mu (G)$$ is NP-complete and relies on the fact that computing $$\alpha (G)$$ is NP-hard (Mosca, Graphs Combinat 18:367-379, ). A well known result of Hammer et al. (SIAM J Alg Disc Math 3(4):511-522, ). states that the vertex-set of a graph $$G$$ can be efficiently and uniquely partitioned in two subsets (possibly empty) $$A$$ and $$B$$ , such that $$G[A]$$ has the König-Egerváry property while $$G[B]$$ can be covered by pairwise disjoint edges and odd cycles: furthermore, one has $$\alpha (G) = \alpha (G[A]) + \alpha (G[B])$$ , where computing $$\alpha (G[A])$$ can be done in polynomial time. For that let us call $$essential$$ those graphs which can be covered by pairwise disjoint edges and odd cycles (in particular computing $$\alpha (G)$$ remains NP-hard for such graphs). This paper shows that: (i) for every essential graph $$G$$ , checking if $$\alpha (G)=\mu (G)$$ can be done in polynomial time; (ii) essential graphs for which $$\alpha (G)=\mu (G)$$ can be recognized in polynomial time and for such graph a maximum stable set can be computed in polynomial time; (iii) a new characterization of graphs which have the König-Egerváry property can be derived in that context. [ABSTRACT FROM AUTHOR]

This paper presents the finding of Maximum Matching and Maximal Matching Cardinality in various Graphs G(V,E) where V is the set of Vertices and E is the set of Edges. Maximum Matching is the collection of Maximum non-adjacent edges. Maximal Matching is the collection of minimum possible collection of nonadjacent edges. Maximum Matching Cardinality implies the Maximum possible number of non-adjacent edges in the Graph. Maximal Matching Cardinality implies the minimum possible number of non-adjacent edges. Here it analyses which Graph proceeds the same value for Maximum Matching and Maximal Matching. It also tells about the relation between the number of edges as well as the vertices and Maximum Matching Cardinality and Maximal Matching Cardinality by using the different Graphs. [ABSTRACT FROM AUTHOR]

Recently, an ancient slime mold, Physarum polycephalum, has been proved being capable of finding shortest path in physical maze environment, which inspires researchers to extract the core foraging mechanism -- positive feedback -- to simulate or model such intelligent behavior. Among most wellknown mathematical models developed so far, physarum solver, has been adopted and extended to solve a plethora of optimization problems in different fields, including computer science, operations research and transportation etc. In this paper, we first adopt and apply a variant of modified physarum solver, called iterative physarum model, to solve bipartite matching problem. Specifically, the maximum bipartite matching problem is first equivalently transformed to single-source single-sink maximum flow problem. Then the iterative physarum model is used to solve the maximum flow problem adaptively. As iterative physarum solver does not involve solving the systems of linear equations associated with global network flow balance constraints, time complexity of updating node status for one iteration can be reduced from O(n3) to O(m), where n and m are numbers of nodes and edges in the graph, respectively. Extensive numerical studies on both sparse and complete bipartite graphs demonstrate the validity and efficiency of this method [ABSTRACT FROM AUTHOR]

Combinatorial problems are a fundamental research subject of theoretical computer science, and for a general graph many combinatorial problems are NP-hard and even #P-complete. Thus, it is interesting to seek or design special graphs for which these difficult combinatorial problems can be exactly solved. In this paper, we study some combinatorial problems for the Farey graphs, which are translated from Farey sequences and have received considerable attention from the scientific community. We determine exactly the domination number, the independence number, and the matching number. Moreover, we derive exact or recursive solutions to the number of minimum dominating sets, the number of dominating sets, the number of maximum independent sets, the number of independent sets, the number of maximum matchings, as well as the number of matchings. Finally, we obtain explicit expressions for the number of acyclic orientations and the number of root-connected acyclic orientations. Since the considered combinatorial problems have found wide applications in diverse fields, such as network science and graph data miming, this work is helpful for deepening our understanding of the applications for these combinatorial problems. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the diversity-aware fair k -supplier problem, which involves selecting k facilities from a set F that consists of m disjoint groups, subject to a constraint on the maximum number of facilities selected from each group. The goal is to ensure fairness in the selection process and avoids any demographic group from over-representation. While the classical k -supplier problem is known to be NP-hard to solve and is even NP-hard to approximate within a factor of less than 3, we present an efficient 5-approximation algorithm for the diversity-aware k -supplier problem based on maximum matching. [ABSTRACT FROM AUTHOR]

Revealing the community structure in social networks witnessed a determined effort. In this respect, a different category of social network can be handled, such as, dynamic social networks, social networks with node attributes, etc. In this article, we introduce a new method to solve this thriving issue in the social network with node attributes. This latter can be represented by a bipartite graph, which consists of a two sets of nodes and edges connecting these nodes. The tendency of people with similar node attributes leads to the hidden information of clusters or communities. A wealthy number of community-detection algorithms have been proposed for bipartite graphs and applied to several domains in the literature. To palliate some of the highlighted shortcomings, we introduce a new approach, called Fast-Bi Community Detection (FBCD), that aims to an efficient community detection in social networks. The main idea of this approach is to explore the set of maximum matching in the bipartite graph in order to reduce the complexity of our algorithm. The carried out experiments show the high quality of the obtained communities versus those by the pioneering ones of the literature. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Harbin Institute of Technology. Social Sciences Edition / Haerbin Gongye Daxue Xuebao. Shehui Kexue Ban is the property of Harbin Institute of Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The Apollonian networks display the remarkable power-law and small-world properties as observed in most realistic networked systems. Their dual graphs are extended Tower of Hanoi graphs, which are obtained from the Tower of Hanoi graphs by adding a special vertex linked to all its three extreme vertices. In this paper, we study analytically maximum matchings and minimum dominating sets in Apollonian networks and their dual graphs, both of which have found vast applications in various fields, e.g. structural controllability of complex networks. For both networks, we determine their matching number, domination number, the number of maximum matchings, as well as the number of minimum dominating sets. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with vertex set V ( G ) . A set S ⊆ V ( G ) is independent if no two vertices from S are adjacent. The graph G is known to be König–Egerváry if α ( G ) + μ ( G ) = | V ( G ) | , where α ( G ) denotes the size of a maximum independent set and μ ( G ) is the cardinality of a maximum matching. A nonempty collection Γ of maximum independent sets is König–Egerváry if | ⋃ Γ | + | ⋂ Γ | = 2 α ( G ) (Jarden et al., 2015). In this paper, we prove that G is a König–Egerváry graph if and only if for every two maximum independent sets S 1 , S 2 of G , there is a matching from V ( G ) − S 1 ∪ S 2 into S 1 ∩ S 2 . Moreover, the same is true, when instead of two sets S 1 and S 2 we consider an arbitrary König–Egerváry collection. [ABSTRACT FROM AUTHOR]

In 1965, Jack Edmonds proposed his celebrated polynomial-time algorithm to find a maximum matching in a graph. It is well-known that finding a maximum matching in G is equivalent to finding a maximum independent set in the line graph of G . For general graphs, the maximum independent set problem is NP-hard. What makes this problem easy in the class of line graphs and what other restrictions can lead to an efficient solution of the problem? In the present paper, we analyse these and related questions. We also review various techniques that may lead to efficient algorithms for the maximum independent set problem in restricted graph families, with a focus given to augmenting graphs and graph transformations. Both techniques have been used in the solution of Edmonds to the maximum matching problem, i.e. in the solution to the maximum independent set problem in the class of line graphs. We survey various results that exploit these techniques beyond the line graphs. [ABSTRACT FROM AUTHOR]

The size and number of maximum matchings in a network have found a large variety of applications in many fields. As a ubiquitous property of diverse real systems, power-law degree distribution was shown to have a profound influence on size of maximum matchings in scale-free networks, where the size of maximum matchings is small and a perfect matching often does not exist. In this paper, we study analytically the maximum matchings in two scale-free networks with identical degree sequence, and show that the first network has no perfect matchings, while the second one has many. For the first network, we determine explicitly the size of maximum matchings, and provide an exact recursive solution for the number of maximum matchings. For the second one, we design an orientation and prove that it is Pfaffian, based on which we derive a closed-form expression for the number of perfect matchings. Moreover, we demonstrate that the entropy for perfect matchings is equal to that corresponding to the extended Sierpiński graph with the same average degree as both studied scale-free networks. Our results indicate that power-law degree distribution alone is not sufficient to characterize the size and number of maximum matchings in scale-free networks. [ABSTRACT FROM AUTHOR]

Node-disjoint paths have played an important role in the study of routing, reliability, and fault tolerance of an interconnection network. In this paper, we give a necessary and sufficient condition, which can be verified in O ( m n 1.5 ) time, for the existence of m node-disjoint shortest paths from one source node to other m (not necessarily distinct) target nodes, respectively, in an n -dimensional folded hypercube, where m ≤ n + 1 . Moreover, when the condition holds, the m node-disjoint shortest paths can be constructed in optimal O ( mn ) time. In the situation that all of the source node and target nodes are mutually distinct, brute-force computations show that the probability of existence of the m node-disjoint shortest paths in an n -dimensional folded hypercube is not less than 100%, 86%, 86%, 92%, and 94% for ( n , m ) = ( 3 , 4 ) , ( 4 , 4 ) , ( 5 , 6 ) , ( 6 , 6 ) , and (7, 8), respectively. [ABSTRACT FROM AUTHOR]

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one-by-one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O(log2 n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(logn) lower bound. The previous best strategy known achieved amortized O(√n) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than the trivial O(n) bound was known except in special cases. Our analysis immediately implies the same upper bound of O(log2 n) reassignments for the capacitated assignment problem, where each vertex on the static side of the bipartition is initialized with the capacity to serve a number of vertices. We also analyze the problem of minimizing the maximum server load. We show that if the final graph has maximum server load L, then the SAP protocol makes amortized O(min{L log2 n,√n log n}) reassignments. We also show that this is close to tight, because Ω(min{L, √n}) reassignments can be necessary. [ABSTRACT FROM AUTHOR]