China
Africa
Explore chapters and articles related to this topic
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
Given the success of LP-based methods, it seems natural to ask if more general mathematical programming methods can be used to design approximation algorithms for difficult optimization problems. After all, convex programming problems admit efficient algorithms (in theory). Moreover, semidefinite programming methods were used by Lovász [1] to find the Shannon capacity of a graph and Grötschel et al. [2] to design a polynomial-time algorithm for finding a maximum independent set in a perfect graph. However, the power of convex (specifically, semidefinite) programming methods was illustrated by Goemans and Williamson [3] in their pioneering work on the MAXCUT problem. Since then, researchers have investigated the use of semidefinite programming in various problems such as graph coloring [4] and betweenness [5], and graph bisection [6].
Modeling and Simulation Tools for Mobile Ad Hoc Networks
Published in Jonathan Loo, Jaime Lloret Mauri, Jesús Hamilton Ortiz, Mobile Ad Hoc Networks, 2016
Kayhan Erciyes, Orhan Dagdeviren, Deniz Cokuslu, Onur Yılmaz, Hasan Gumus
An independent set (IS) is a set of nodes in which none of the nodes are adjacent. If this set cannot be extended by adding a new node, then IS is called the maximal IS. The IS with the greatest number of nodes is called the maximum IS. In Figure 3.6a, six gray-filled nodes are the elements of the maximal IS. However, this set cannot be extended by adding a new node; removing some nodes from this set and adding other nodes may increase the size. In Figure 3.6b, the maximum IS with eight nodes is shown. In the weighted version of this problem, a weight is assigned to each node, and maximizing the total weight of this set is targeted. In Figure 3.6c, the maximum weighted IS having a total weight of 56 is depicted.
A Hybrid Genetic Approach for Channel Reuse in Multiple Access Telecommunication Networks
Published in Witold Pedrycz, Athanasios Vasilakos, Computational Intelligence in Telecommunications Networks, 2018
Ioannis E. Kassotakis, Maria E. Markaki, Athanasios V. Vasilakos
In this section we briefly state the graph coloring problem16 and show how the ICRP can be formulated as a graph coloring problem. A graph is a set of points called vertices with connections called edges between pairs of vertices. Given a graph G = (V, E) with vertex set V and edge set E and given a positive integer k, one has to find a k-coloring of G, i.e., a partition of V into k independent sets V1, …, Vk (a set Vi of vertices is called independent if no two vertices in Vi are linked by an edge in G). If such a partition exists, G is called k-colorable.
An evolutionary algorithm for the robust maximum weighted independent set problem
Published in Automatika, 2020
As already announced, in this paper, we study the maximum weighted independent set problem. Its conventional variant is very well known and treated in many textbooks, e.g.[10,11]. We give here some basic definitions for convenience. Let be an undirected graph, where V is the set of vertices and E the set of edges. An independent set of G is a subset X of V such that no two vertices in X are adjacent (connected by an edge from E).Let be an undirected graph whose vertices have weights. Suppose that all weights are positive real numbers. A maximum weighted independent set of G is an independent set of G whose sum of vertex weights is as large as possible.The problem of finding a maximum weighted independent set in a given weighted graph is called the (conventional) maximum weighted independent set problem (the MWIS problem).
Distributed maximal independent set computation driven by finite-state dynamics
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Eric Goles, Laura Leal, Pedro Montealegre, Ivan Rapaport, Martín Ríos-Wilson
A set of nodes S is called an independent set if the graph induced by it has no edges. An inclusion-maximal independent set is simply called maximal independent set. The cardinality of an independent set of maximal cardinality is denoted , and is called the independence number of G. The problem of computing is NP-Hard. The range of its value goes from 1 for the complete graph, to n−1 for the case of the star graph. There are a number of combinatorial lower bounds for with respect to some graph parameters. In this article, we make use of the following simple result.
Roof model recommendation for complex buildings based on combination rules and symmetry features in footprints
Published in International Journal of Digital Earth, 2018
Xuke Hu, Hongchao Fan, Alexey Noskov
We assume that building footprints consisting of rectangle structures are quite common in real environments. In order to achieve reasonable partitions from footprints, an advanced MNC partitioning algorithm is used. A reasonable partition means each rectangle in a partition correctly corresponds to a roof primitive of a true building roof. We assume that the horizontal and vertical edges of rectilinear polygons are parallel to x-axis and y-axis, respectively. The conventional MNC algorithm (Wu and Sahni 1994) consists of the following six steps: Identify the concave vertexes of a rectilinear polygon.Generate vertical and horizontal chords by connecting two concave vertexes that have an equal x and y coordinate, respectively. Due to the noise in footprints, we define that two x or y coordinates are equal when their difference is below a threshold of 0.3 m. The concave vertex whose x or y coordinate is unequal to the x or y coordinate of any other concave vertexes is called free concave vertex.Obtain a maximum matching (MM) by using the Hungarian algorithm (Kuhn 1956). We treat vertical and horizontal chords as the left and right parts of a bipartite graph, respectively, where each chord is denoted by an endpoint. Then, we add an edge to connect two chords if they are intersected. Therefore, a bipartite graph can be denoted by , where H, V, and E represent horizontal chords, vertical chords, and the edges among them, respectively. A matching in a bipartite graph is a set of edges chosen in such a way that no two edges share an endpoint. An MM is a matching of a maximum number of edges.Find a maximum independent set (MIS) from the bipartite graph (Wu and Sahni 1994). An independent set in a graph is a set of endpoints chosen in such a way that no two endpoints are connected by an edge. An MIS is an independent set of maximum number of endpoints.Draw the chords in MIS to partition the polygon.Draw a horizontal or vertical line segment from the free concave vertexes to the nearest edge.