Search results for: Usage Problem

Authors: Zohreh O. Akbari

Abstract:

In this paper a deterministic polynomial-time algorithm is presented for the Clique problem. The case is considered as the problem of omitting the minimum number of vertices from the input graph so that none of the zeroes on the graph-s adjacency matrix (except the main diagonal entries) would remain on the adjacency matrix of the resulting subgraph. The existence of a deterministic polynomial-time algorithm for the Clique problem, as an NP-complete problem will prove the equality of P and NP complexity classes.

Keywords: Clique problem, Deterministic Polynomial-time Algorithm, Equality of P and NP Complexity Classes.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1774

Authors: Ben Mohamed Ahemed Mohamed, Yassine Adnan

Abstract:

The problem of bin-packing in two dimensions (2BP) consists in placing a given set of rectangular items in a minimum number of rectangular and identical containers, called bins. This article treats the case of objects with a free orientation of 90Ôùª. We propose an approach of resolution combining optimization by colony of ants (ACO) and the heuristic method IMA to resolve this NP-Hard problem.

Keywords: Ant colony algorithm, bin-packing problem, heuristics methods.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1793

Authors: Shrikrishan Yadav, Akhilesh Saini, Krishna Chandra Roy

Abstract:

The electromagnetic spectrum is a natural resource and hence well-organized usage of the limited natural resources is the necessities for better communication. The present static frequency allocation schemes cannot accommodate demands of the rapidly increasing number of higher data rate services. Therefore, dynamic usage of the spectrum must be distinguished from the static usage to increase the availability of frequency spectrum. Cognitive radio is not a single piece of apparatus but it is a technology that can incorporate components spread across a network. It offers great promise for improving system efficiency, spectrum utilization, more effective applications, reduction in interference and reduced complexity of usage for users. Cognitive radio is aware of its environmental, internal state, and location, and autonomously adjusts its operations to achieve designed objectives. It first senses its spectral environment over a wide frequency band, and then adapts the parameters to maximize spectrum efficiency with high performance. This paper only focuses on the analysis of Bit-Error-Rate in cognitive radio by using Particle Swarm Optimization Algorithm. It is theoretically as well as practically analyzed and interpreted in the sense of advantages and drawbacks and how BER affects the efficiency and performance of the communication system.

Keywords: BER, Cognitive Radio, Environmental Parameters, PSO, Radio spectrum, Transmission Parameters

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2114

Authors: Maricar G. Misola, Bryan B. Navarro

Abstract:

Facility Layout Problem (FLP) is one of the essential problems of several types of manufacturing and service sector. It is an optimization problem on which the main objective is to obtain the efficient locations, arrangement and order of the facilities. In the literature, there are numerous facility layout problem research presented and have used meta-heuristic approaches to achieve optimal facility layout design. This paper presented genetic algorithm to solve facility layout problem; to minimize total cost function. The performance of the proposed approach was verified and compared using problems in the literature.

Keywords: Facility Layout Problem, Genetic Algorithm, Material Handling Cost, Meta-heuristic Approach.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 4690

Authors: Aldy Gunawan, Kien Ming Ng, Kim Leng Poh

Abstract:

This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.

Keywords: Timetabling problem, mathematical programming model, hybrid algorithm, simulated annealing.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 4527

Authors: Takayuki Shiina

Abstract:

We consider power system expansion planning under uncertainty. In our approach, integer programming and stochastic programming provide a basic framework. We develop a multistage stochastic programming model in which some of the variables are restricted to integer values. By utilizing the special property of the problem, called block separable recourse, the problem is transformed into a two-stage stochastic program with recourse. The electric power capacity expansion problem is reformulated as the problem with first stage integer variables and continuous second stage variables. The L-shaped algorithm to solve the problem is proposed.

Keywords: electric power capacity expansion problem, integerprogramming, L-shaped method, stochastic programming

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1784

Authors: Jian Du, Shui Hong Hong, Lu Meng, Qing Wei Meng

Abstract:

This work addresses the problem of optimizing completely batch water-using network with multiple contaminants where the flow change caused by mass transfer is taken into consideration for the first time. A mathematical technique for optimizing water-using network is proposed based on source-tank-sink superstructure. The task is to obtain the freshwater usage, recycle assignments among water-using units, wastewater discharge and a steady water-using network configuration by following steps. Firstly, operating sequences of water-using units are determined by time constraints. Next, superstructure is simplified by eliminating the reuse and recycle from water-using units with maximum concentration of key contaminants. Then, the non-linear programming model is solved by GAMS (General Algebra Model System) for minimum freshwater usage, maximum water recycle and minimum wastewater discharge. Finally, numbers of operating periods are calculated to acquire the steady network configuration. A case study is solved to illustrate the applicability of the proposed approach.

Keywords: Completely batch process, flow change, multiple contaminants, water-using network.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1403

Authors: M. G. M. Khan, V. D. Prasad, D. K. Rao

Abstract:

In this manuscript, we discuss the problem of determining the optimum stratification of a study (or main) variable based on the auxiliary variable that follows a uniform distribution. If the stratification of survey variable is made using the auxiliary variable it may lead to substantial gains in precision of the estimates. This problem is formulated as a Nonlinear Programming Problem (NLPP), which turn out to multistage decision problem and is solved using dynamic programming technique.

Keywords: Auxiliary variable, Dynamic programming technique, Nonlinear programming problem, Optimum stratification, Uniform distribution.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2065

Authors: Dhany Saputra, Dayang R. A. Rambli, Oi Mean Foong

Abstract:

In this paper, we propose an improvement of pattern growth-based PrefixSpan algorithm, called I-PrefixSpan. The general idea of I-PrefixSpan is to use sufficient data structure for Seq-Tree framework and separator database to reduce the execution time and memory usage. Thus, with I-PrefixSpan there is no in-memory database stored after index set is constructed. The experimental result shows that using Java 2, this method improves the speed of PrefixSpan up to almost two orders of magnitude as well as the memory usage to more than one order of magnitude.

Keywords: ArrayList, ArrayIntList, minimum support, sequence database, sequential patterns.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1532

Authors: Buthainah Fahran Al-Dulaimi, Hamza A. Ali

Abstract:

The well known NP-complete problem of the Traveling Salesman Problem (TSP) is coded in genetic form. A software system is proposed to determine the optimum route for a Traveling Salesman Problem using Genetic Algorithm technique. The system starts from a matrix of the calculated Euclidean distances between the cities to be visited by the traveling salesman and a randomly chosen city order as the initial population. Then new generations are then created repeatedly until the proper path is reached upon reaching a stopping criterion. This search is guided by a solution evaluation function.

Keywords: Genetic algorithms, traveling salesman problem solving, optimization.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2504

Authors: Carsten Röcker

Abstract:

This paper provides an introduction into the evolution of information and communication technology and illustrates its usage in the work domain. The paper is sub-divided into two parts. The first part gives an overview over the different phases of information processing in the work domain. It starts by charting the past and present usage of computers in work environments and shows current technological trends, which are likely to influence future business applications. The second part starts by briefly describing, how the usage of computers changed business processes in the past, and presents first Ambient Intelligence applications based on identification and localization information, which are already used in the production and retail sector. Based on current systems and prototype applications, the paper gives an outlook of how Ambient Intelligence technologies could change business processes in the future.

Keywords: Ambient Intelligence, Ubiquitous Computing, Business Applications, Radio Frequency Identification (RFID).

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1881

Authors: Carsten Röcker

Abstract:

This paper provides an introduction into the evolution of information and communication technology and illustrates its usage in the work domain. The paper is sub-divided into two parts. The first part gives an overview over the different phases of information processing in the work domain. It starts by charting the past and present usage of computers in work environments and shows current technological trends, which are likely to influence future business applications. The second part starts by briefly describing, how the usage of computers changed business processes in the past, and presents first Ambient Intelligence applications based on identification and localization information, which are already used in the production and retail sector. Based on current systems and prototype applications, the paper gives an outlook of how Ambient Intelligence technologies could change business processes in the future.

Keywords: Ambient Intelligence, Ubiquitous Computing, Business Applications, Radio Frequency Identification (RFID)

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1831

Authors: Liudmyla Koliechkina, Olena Dvirna

Abstract:

The statement of the multi-objective optimization problem on combinatorial configurations is formulated, and the approach to its solution is proposed. The problem is of interest as a combinatorial optimization one with many criteria, which is a model of many applied tasks. The approach to solving the multi-objective optimization problem on combinatorial configurations consists of two stages; the first is the reduction of the multi-objective problem to the single criterion based on existing multi-objective optimization methods, the second stage solves the directly replaced single criterion combinatorial optimization problem by the horizontal combinatorial method. This approach provides the optimal solution to the multi-objective optimization problem on combinatorial configurations, taking into account additional restrictions for a finite number of steps.

Keywords: Discrete set, linear combinatorial optimization, multi-objective optimization, multipermutation, Pareto solutions, partial permutation set, permutation, structural graph.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 620

Authors: I. Mahdavi, A. Jazayeri, M. Jahromi, R. Jafari, H. Iranmanesh

Abstract:

One of the most important problems in production planning of flexible manufacturing system (FMS) is machine tool selection and operation allocation problem that directly influences the production costs and times .In this paper minimizing machining cost, set-up cost and material handling cost as a multi-objective problem in flexible manufacturing systems environment are considered. We present a 0-1 integer linear programming model for the multiobjective machine tool selection and operation allocation problem and due to the large scale nature of the problem, solving the problem to obtain optimal solution in a reasonable time is infeasible, Paretoant colony optimization (P-ACO) approach for solving the multiobjective problem in reasonable time is developed. Experimental results indicate effectiveness of the proposed algorithm for solving the problem.

Keywords: Flexible manufacturing system, Production planning, Machine tool selection, Operation allocation, Multiobjective optimization, Metaheuristic.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1873

Authors: Jindřiška Šedová, Miloš Šeda

Abstract:

This paper summarizes and compares approaches to solving the knapsack problem and its known application in capital budgeting. The first approach uses deterministic methods and can be applied to small-size tasks with a single constraint. We can also apply commercial software systems such as the GAMS modelling system. However, because of NP-completeness of the problem, more complex problem instances must be solved by means of heuristic techniques to achieve an approximation of the exact solution in a reasonable amount of time. We show the problem representation and parameter settings for a genetic algorithm framework.

Keywords: Capital budgeting, knapsack problem, GAMS, heuristic method, genetic algorithm.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1701

Authors: Tami Alghamdi, Terence Soule

Abstract:

To study how to transfer knowledge from multiple source problems to the target problem, we modeled the Transfer Learning (TL) process using Genetic Algorithms as the model solver. TL is the process that aims to transfer learned data from one problem to another problem. The TL process aims to help Machine Learning (ML) algorithms find a solution to the problems. The Genetic Algorithms (GA) give researchers access to information that we have about how the old problem is solved. In this paper, we have five different source problems, and we transfer the knowledge to the target problem. We studied different scenarios of the target problem. The results showed that combined knowledge from multiple source problems improves the GA performance. Also, the process of combining knowledge from several problems results in promoting diversity of the transferred population.

Keywords: Transfer Learning, Multiple Sources, Knowledge Transfer, Domain Adaptation, Source, Target.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 276

Authors: Javier Roca, Etienne Pugnaghi, Gaëtan Libert

Abstract:

We introduce an extended resource leveling model that abstracts real life projects that consider specific work ranges for each resource. Contrary to traditional resource leveling problems this model considers scarce resources and multiple objectives: the minimization of the project makespan and the leveling of each resource usage over time. We formulate this model as a multiobjective optimization problem and we propose a multiobjective genetic algorithm-based solver to optimize it. This solver consists in a two-stage process: a main stage where we obtain non-dominated solutions for all the objectives, and a postprocessing stage where we seek to specifically improve the resource leveling of these solutions. We propose an intelligent encoding for the solver that allows including domain specific knowledge in the solving mechanism. The chosen encoding proves to be effective to solve leveling problems with scarce resources and multiple objectives. The outcome of the proposed solvers represent optimized trade-offs (alternatives) that can be later evaluated by a decision maker, this multi-solution approach represents an advantage over the traditional single solution approach. We compare the proposed solver with state-of-art resource leveling methods and we report competitive and performing results.

Keywords: Intelligent problem encoding, multiobjective decision making, evolutionary computing, RCPSP, resource leveling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 4151

Authors: Nayera E. El-Gharably, Khaled S. El-Kilany, Aziz E. El-Sayed

Abstract:

A key element of many distribution systems is the routing and scheduling of vehicles servicing a set of customers. A wide variety of exact and approximate algorithms have been proposed for solving the vehicle routing problems (VRP). Exact algorithms can only solve relatively small problems of VRP, which is classified as NP-Hard. Several approximate algorithms have proven successful in finding a feasible solution not necessarily optimum. Although different parts of the problem are stochastic in nature; yet, limited work relevant to the application of discrete event system simulation has addressed the problem. Presented here is optimization using simulation of VRP; where, a simplified problem has been developed in the ExtendSimTM simulation environment; where, ExtendSimTM evolutionary optimizer is used to minimize the total transportation cost of the problem. Results obtained from the model are very satisfactory. Further complexities of the problem are proposed for consideration in the future.

Keywords: Discrete event system simulation, optimization using simulation, vehicle routing problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 5798

Authors: S. Nasri, H. Bouziri

Abstract:

Disasters are quite experienced in our days. They are caused by floods, landslides, and building fires that is the main objective of this study. To cope with these unexpected events, precautions must be taken to protect human lives. The emphasis on disposal work focuses on the resolution of the evacuation problem in case of no-notice disaster. The problem of evacuation is listed as a dynamic network flow problem. Particularly, we model the evacuation problem as an earliest arrival flow problem with load dependent transit time. This problem is classified as NP-Hard. Our challenge here is to propose a metaheuristic solution for solving the evacuation problem. We define our objective as the maximization of evacuees during earliest periods of a time horizon T. The objective provides the evacuation of persons as soon as possible. We performed an experimental study on emergency evacuation from the tunisian children’s hospital. This work prompts us to look for evacuation plans corresponding to several situations where the network dynamically changes.

Keywords: Dynamic network flow, Load dependent transit time, Evacuation strategy, Earliest arrival flow problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1767

Authors: M. Dinakaran, P. Balasubramanie

Abstract:

With the demand of mobility by users, wireless technologies have become the hotspot developing arena. Internet Engineering Task Force (IETF) working group has developed Mobile IP to support node mobility. The concept of node mobility indicates that in spite of the movement of the node, it is still connected to the internet and all the data transactions are preserved. It provides location-independent access to Internet. After the incorporation of host mobility, network mobility has undergone intense research. There are several intricacies faced in the real world implementation of network mobility significantly the problem of nested networks and their consequences. This article is concerned regarding a problem of nested network called pinball route problem and proposes a solution to eliminate the above problem. The proposed mechanism is implemented using NS2 simulation tool and it is found that the proposed mechanism efficiently reduces the overload caused by the pinball route problem.

Keywords: Mobile IP, Pinball routing problem, NEMO

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1814

Authors: N. Rugthaicharoencheep, S. Auchariyamet

Abstract:

Optimal capacitor allocation in distribution systems has been studied for a long times. It is an optimization problem which has an objective to define the optimal sizes and locations of capacitors to be installed. In this works, an overview of capacitor placement problem in distribution systems is briefly introduced. The objective functions and constraints of the problem are listed and the methodologies for solving the problem are summarized.

Keywords: Capacitor Placement, Distribution Systems, Optimization Techniques

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2381

Authors: Pramod Goyal, S. K. Saxena

Abstract:

The convergence of heterogeneous wireless access technologies characterizes the 4G wireless networks. In such converged systems, the seamless and efficient handoff between different access technologies (vertical handoff) is essential and remains a challenging problem. The heterogeneous co-existence of access technologies with largely different characteristics creates a decision problem of determining the “best" available network at “best" time to reduce the unnecessary handoffs. This paper proposes a dynamic decision model to decide the “best" network at “best" time moment to handoffs. The proposed dynamic decision model make the right vertical handoff decisions by determining the “best" network at “best" time among available networks based on, dynamic factors such as “Received Signal Strength(RSS)" of network and “velocity" of mobile station simultaneously with static factors like Usage Expense, Link capacity(offered bandwidth) and power consumption. This model not only meets the individual user needs but also improve the whole system performance by reducing the unnecessary handoffs.

Keywords: Dynamic decision model, Seamless handoff, Vertical handoff, Wireless networks

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2019

Authors: Luka Pavlič, Marjan Heričko

Abstract:

E-services have significantly changed the way of doing business in recent years. We can, however, observe poor use of these services. There is a large gap between supply and actual eservices usage. This is why we started a project to provide an environment that will encourage the use of e-services. We believe that only providing e-service does not automatically mean consumers would use them. This paper shows the origins of our project and its current position. We discuss the decision of using semantic web technologies and their potential to improve e-services usage. We also present current knowledge base and its real-world classification. In the paper, we discuss further work to be done in the project. Current state of the project is promising.

Keywords: E-Services, E-Services Repository, Ontologies, Semantic Web

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1364

Authors: Birol Gülnar, Hacer Aker

Abstract:

Student-s movements have been going increasing in last decades. International students can have different psychological and sociological problems in their adaptation process. Depression is one of the most important problems in this procedure. This research purposed to reveal level of foreign students- depression, kinds of interpersonal communication networks (host/ethnic interpersonal communication) and media usage (host/ethnic media usage). Additionally study aimed to display the relationship between depression and communication (host/ethnic interpersonal communication and host/ethnic media usage) among foreign university students. A field research was performed among 283 foreign university students who have been attending 8 different universities in Turkey. A purposeful sampling technique was used in this research cause of data collect facilities. Results indicated that 58.3% of foreign students- depression stage was “intermediate" while 33.2% of foreign students- depression level was “low". Add to this, host interpersonal communication behaviors and Turkish web sites usages were negatively and significantly correlated with depression.

Keywords: International students, depression, interpersonal communication behaviors, media using.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2842

Authors: Divyesh Patel, Tanuja Srivastava

Abstract:

This paper considers the NP-hard problem of reconstructing binary matrices satisfying exactly-1-4-adjacency constraint from its row and column projections. This problem is formulated into a maximization problem. The objective function gives a measure of adjacency constraint for the binary matrices. The maximization problem is solved by the simulated annealing algorithm and experimental results are presented.

Keywords: Discrete Tomography, exactly-1-4-adjacency, simulated annealing.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2419

Authors: Narendra M. Shekokar, Satish R. Devane

Abstract:

In a recent year usage of VoIP subscription has increased tremendously as compare to Public Switching Telephone System(PSTN). A VoIP subscriber would like to know the exact tariffs of the calls made using VoIP. As the usage increases, the rate of fraud is also increases, causing users complain about excess billing. This in turn hampers the growth of VoIP .This paper describe the common frauds and attack on VoIP based system and make an attempt to solve the billing attack by creating secured channel between caller and callee.

Keywords: VoIP, Billing-fraud, SSL/TLS, MITM, Replay-attack.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1614

Authors: Farhad F. Yusifov

Abstract:

With the explosive growth of data available on the Internet, personalization of this information space become a necessity. At present time with the rapid increasing popularity of the WWW, Websites are playing a crucial role to convey knowledge and information to the end users. Discovering hidden and meaningful information about Web users usage patterns is critical to determine effective marketing strategies to optimize the Web server usage for accommodating future growth. The task of mining useful information becomes more challenging when the Web traffic volume is enormous and keeps on growing. In this paper, we propose a intelligent model to discover and analyze useful knowledge from the available Web log data.

Keywords: Clustering, Self organizing map, Web log files, Web traffic.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1565

Authors: R. Hashemi, M.H.Kargarnovin

Abstract:

This paper presents the identification of the impact force acting on a simply supported beam. The force identification is an inverse problem in which the measured response of the structure is used to determine the applied force. The identification problem is formulated as an optimization problem and the genetic algorithm is utilized to solve the optimization problem. The objective function is calculated on the difference between analytical and measured responses and the decision variables are the location and magnitude of the applied force. The results from simulation show the effectiveness of the approach and its robustness vs. the measurement noise and sensor location.

Keywords: Genetic Algorithm, Inverse problem, Optimization, Vibration.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1510

Authors: Broderick Crawford, Ricardo Soto, Natalia Berrios, Eduardo Olguin

Abstract:

In this paper, we present a binary cat swarm optimization for solving the Set covering problem. The set covering problem is a well-known NP-hard problem with many practical applications, including those involving scheduling, production planning and location problems. Binary cat swarm optimization is a recent swarm metaheuristic technique based on the behavior of discrete cats. Domestic cats show the ability to hunt and are curious about moving objects. The cats have two modes of behavior: seeking mode and tracing mode. We illustrate this approach with 65 instances of the problem from the OR-Library. Moreover, we solve this problem with 40 new binarization techniques and we select the technical with the best results obtained. Finally, we make a comparison between results obtained in previous studies and the new binarization technique, that is, with roulette wheel as transfer function and V3 as discretization technique.

Keywords: Binary cat swarm optimization, set covering problem, metaheuristic, binarization methods.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2299

Authors: S. Balaji, V. Swaminathan, K. Kannan

Abstract:

The Minimum Weighted Vertex Cover (MWVC) problem is a classic graph optimization NP - complete problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the minimum weighted vertex cover problem is to find a vertex set S V whose total weight is minimum subject to every edge of G has at least one end point in S. In this paper an effective algorithm, called Support Ratio Algorithm (SRA), is designed to find the minimum weighted vertex cover of a graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the SRA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.

Keywords: Weighted vertex cover, vertex support, approximation algorithms, NP-complete problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3838