**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**694

# Search results for: Weighted vertex cover

##### 694 An Effective Algorithm for Minimum Weighted Vertex Cover Problem

**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.

##### 693 Approximating Maximum Weighted Independent Set Using Vertex Support

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

**Abstract:**

**Keywords:**
weighted independent set,
vertex cover,
vertex support,
heuristic,
NP - hard problem.

##### 692 Optimization of Unweighted Minimum Vertex Cover

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

**Abstract:**

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

##### 691 Connected Vertex Cover in 2-Connected Planar Graph with Maximum Degree 4 is NP-complete

**Authors:**
Priyadarsini P. L. K,
Hemalatha T.

**Abstract:**

**Keywords:**
NP-complete,
2-Connected planar graph,
block,
cut vertex

##### 690 Induced Graphoidal Covers in a Graph

**Authors:**
K. Ratan Singh,
P. K. Das

**Abstract:**

An induced graphoidal cover of a graph G is a collection ψ of (not necessarily open) paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ, every edge of G is in exactly one path in ψ and every member of ψ is an induced cycle or an induced path. The minimum cardinality of an induced graphoidal cover of G is called the induced graphoidal covering number of G and is denoted by ηi(G) or ηi. Here we find induced graphoidal cover for some classes of graphs.

**Keywords:**
Graphoidal cover,
Induced graphoidal cover,
Induced graphoidal covering number.

##### 689 Induced Acyclic Graphoidal Covers in a Graph

**Authors:**
K. Ratan Singh,
P. K. Das

**Abstract:**

**Keywords:**
Graphoidal cover,
Induced acyclic graphoidal cover,
Induced acyclic graphoidal covering number.

##### 688 Vertex Configurations and Their Relationship on Orthogonal Pseudo-Polyhedra

**Authors:**
Jefri Marzal,
Hong Xie,
Chun Che Fung

**Abstract:**

**Keywords:**
Orthogonal Pseudo Polyhedra,
Vertex configuration

##### 687 The Vertex and Edge Irregular Total Labeling of an Amalgamation of Two Isomorphic Cycles

**Authors:**
Nurdin

**Abstract:**

Suppose G(V,E) is a graph, a function f : V \cup E \to \{1, 2, 3, \cdots, k\} is called the total edge(vertex) irregular k-labelling for G such that for each two edges are different having distinct weights. The total edge(vertex) irregularity strength of G, denoted by tes(G)(tvs(G), is the smallest k positive integers such that G has a total edge(vertex) irregular k-labelling. In this paper, we determined the total edge(vertex) irregularity strength of an amalgamation of two isomorphic cycles. The total edge irregularity strength and the total vertex irregularity strength of two isomorphic cycles on n vertices are \lceil (2n+2)/3 \rceil and \lceil 2n/3 \rceil for n \geq 3, respectively.

**Keywords:**
Amalgamation of graphs,
irregular labelling,
irregularity strength.

##### 686 Generalised Slant Weighted Toeplitz Operator

**Authors:**
S. C. Arora,
Ritu Kathuria

**Abstract:**

**Keywords:**
Slant weighted Toeplitz operator,
weighted multiplicationoperator.

##### 685 Nullity of t-Tupple Graphs

**Authors:**
Khidir R. Sharaf,
Didar A. Ali

**Abstract:**

The nullity η(G) of a graph is the occurrence of zero as an eigenvalue in its spectra. A zero-sum weighting of a graph G is real valued function, say f from vertices of G to the set of real numbers, provided that for each vertex of G the summation of the weights f(w) over all neighborhood w of v is zero for each v in G.A high zero-sum weighting of G is one that uses maximum number of non-zero independent variables. If G is graph with an end vertex, and if H is an induced subgraph of G obtained by deleting this vertex together with the vertex adjacent to it, then, η(G)= η(H). In this paper, a high zero-sum weighting technique and the endvertex procedure are applied to evaluate the nullity of t-tupple and generalized t-tupple graphs are derived and determined for some special types of graphs,

Also, we introduce and prove some important results about the t-tupple coalescence, Cartesian and Kronecker products of nut graphs.

**Keywords:**
Graph theory,
Graph spectra,
Nullity of graphs.

##### 684 GPU-Accelerated Triangle Mesh Simplification Using Parallel Vertex Removal

**Authors:**
Thomas Odaker,
Dieter Kranzlmueller,
Jens Volkert

**Abstract:**

**Keywords:**
Computer graphics,
half edge collapse,
mesh
simplification,
precomputed simplification,
topology preserving.

##### 683 Graphs with Metric Dimension Two-A Characterization

**Authors:**
Sudhakara G,
Hemanth Kumar A.R

**Abstract:**

In this paper, we define distance partition of vertex set of a graph G with reference to a vertex in it and with the help of the same, a graph with metric dimension two (i.e. β (G) = 2 ) is characterized. In the process, we develop a polynomial time algorithm that verifies if the metric dimension of a given graph G is two. The same algorithm explores all metric bases of graph G whenever β (G) = 2 . We also find a bound for cardinality of any distance partite set with reference to a given vertex, when ever β (G) = 2 . Also, in a graph G with β (G) = 2 , a bound for cardinality of any distance partite set as well as a bound for number of vertices in any sub graph H of G is obtained in terms of diam H .

**Keywords:**
Metric basis,
Distance partition,
Metric dimension.

##### 682 A Meta-Heuristic Algorithm for Vertex Covering Problem Based on Gravity

**Authors:**
S. Raja Balachandar,
K.Kannan

**Abstract:**

A new Meta heuristic approach called "Randomized gravitational emulation search algorithm (RGES)" for solving vertex covering problems has been designed. This algorithm is found upon introducing randomization concept along with the two of the four primary parameters -velocity- and -gravity- in physics. A new heuristic operator is introduced in the domain of RGES to maintain feasibility specifically for the vertex covering problem to yield best solutions. The performance of this algorithm has been evaluated on a large set of benchmark problems from OR-library. Computational results showed that the randomized gravitational emulation search algorithm - based heuristic is capable of producing high quality solutions. The performance of this heuristic when compared with other existing heuristic algorithms is found to be excellent in terms of solution quality.

**Keywords:**
Vertex covering Problem,
Velocity,
Gravitational Force,
Newton's Law,
Meta Heuristic,
Combinatorial optimization.

##### 681 Weighted Composition Operators Acting between Kind of Weighted Bergman-Type Spaces and the Bers-Type Space

**Authors:**
Amnah E. Shammahy

**Abstract:**

In this paper, we study the boundedness and compactness of the weighted composition operator W_{u,φ, }which is induced by an holomorphic function *u* and holomorphic self-map *φ*, acting between the *N _{K}*-space and the Bers-type space H

^{∞}

_{α}on the unit disk.

**Keywords:**
Weighted composition operators,
NK-space,
Bers-type space.

##### 680 Dependent Weighted Aggregation Operators of Hesitant Fuzzy Numbers

**Authors:**
Jing Liu

**Abstract:**

In this paper, motivated by the ideas of dependent weighted aggregation operators, we develop some new hesitant fuzzy dependent weighted aggregation operators to aggregate the input arguments taking the form of hesitant fuzzy numbers rather than exact numbers, or intervals. In fact, we propose three hesitant fuzzy dependent weighted averaging(HFDWA) operators, and three hesitant fuzzy dependent weighted geometric(HFDWG) operators based on different weight vectors, and the most prominent characteristic of these operators is that the associated weights only depend on the aggregated hesitant fuzzy numbers and can relieve the influence of unfair hesitant fuzzy numbers on the aggregated results by assigning low weights to those “false” and “biased” ones. Some examples are given to illustrated the efficiency of the proposed operators.

**Keywords:**
Hesitant fuzzy numbers,
hesitant fuzzy dependent weighted averaging(HFDWA) operators,
hesitant fuzzy dependent weighted geometric(HFDWG) operators.

##### 679 Distributed 2-Vertex Connectivity Test of Graphs Using Local Knowledge

**Authors:**
Brahim Hamid,
Bertrand Le Saec,
Mohamed Mosbah

**Abstract:**

The vertex connectivity of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. This work is devoted to the problem of vertex connectivity test of graphs in a distributed environment based on a general and a constructive approach. The contribution of this paper is threefold. First, using a preconstructed spanning tree of the considered graph, we present a protocol to test whether a given graph is 2-connected using only local knowledge. Second, we present an encoding of this protocol using graph relabeling systems. The last contribution is the implementation of this protocol in the message passing model. For a given graph G, where M is the number of its edges, N the number of its nodes and Δ is its degree, our algorithms need the following requirements: The first one uses O(Δ×N2) steps and O(Δ×logΔ) bits per node. The second one uses O(Δ×N2) messages, O(N2) time and O(Δ × logΔ) bits per node. Furthermore, the studied network is semi-anonymous: Only the root of the pre-constructed spanning tree needs to be identified.

**Keywords:**
Distributed computing,
fault-tolerance,
graph relabeling systems,
local computations,
local knowledge,
message passing system,
networks,
vertex connectivity.

##### 678 The Intuitionistic Fuzzy Ordered Weighted Averaging-Weighted Average Operator and its Application in Financial Decision Making

**Authors:**
Shouzhen Zeng

**Abstract:**

**Keywords:**
Intuitionistic fuzzy numbers,
Weighted average,
OWA operator,
Financial decision making

##### 677 The Relative Efficiency of Parameter Estimation in Linear Weighted Regression

**Authors:**
Baoguang Tian,
Nan Chen

**Abstract:**

A new relative efficiency in linear model in reference is instructed into the linear weighted regression, and its upper and lower bound are proposed. In the linear weighted regression model, for the best linear unbiased estimation of mean matrix respect to the least-squares estimation, two new relative efficiencies are given, and their upper and lower bounds are also studied.

**Keywords:**
Linear weighted regression,
Relative efficiency,
Mean matrix,
Trace.

##### 676 A Neighborhood Condition for Fractional k-deleted Graphs

**Authors:**
Sizhong Zhou,
Hongxia Liu

**Abstract:**

Abstract–Let k ≥ 3 be an integer, and let G be a graph of order n with n ≥ 9k +3- 42(k - 1)2 + 2. Then a spanning subgraph F of G is called a k-factor if dF (x) = k for each x ∈ V (G). A fractional k-factor is a way of assigning weights to the edges of a graph G (with all weights between 0 and 1) such that for each vertex the sum of the weights of the edges incident with that vertex is k. A graph G is a fractional k-deleted graph if there exists a fractional k-factor after deleting any edge of G. In this paper, it is proved that G is a fractional k-deleted graph if G satisfies δ(G) ≥ k + 1 and |NG(x) ∪ NG(y)| ≥ 1 2 (n + k - 2) for each pair of nonadjacent vertices x, y of G.

**Keywords:**
Graph,
minimum degree,
neighborhood union,
fractional k-factor,
fractional k-deleted graph.

##### 675 Sample-Weighted Fuzzy Clustering with Regularizations

**Authors:**
Miin-Shen Yang,
Yee-Shan Pan

**Abstract:**

Although there have been many researches in cluster analysis to consider on feature weights, little effort is made on sample weights. Recently, Yu et al. (2011) considered a probability distribution over a data set to represent its sample weights and then proposed sample-weighted clustering algorithms. In this paper, we give a sample-weighted version of generalized fuzzy clustering regularization (GFCR), called the sample-weighted GFCR (SW-GFCR). Some experiments are considered. These experimental results and comparisons demonstrate that the proposed SW-GFCR is more effective than the most clustering algorithms.

**Keywords:**
Clustering; fuzzy c-means,
fuzzy clustering,
sample
weights,
regularization.

##### 674 OWA Operators in Generalized Distances

**Authors:**
José M. Merigó,
Anna M. Gil-Lafuente

**Abstract:**

**Keywords:**
Aggregation operators,
Distance measures,
Quasi- OWA operator.

##### 673 N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs

**Authors:**
R. Anitha,
R. S. Lekshmi

**Abstract:**

**Keywords:**
Decomposition,
Hamilton cycle,
n-sun graph,
perfect matching,
spanning tree.

##### 672 Improved K-Modes for Categorical Clustering Using Weighted Dissimilarity Measure

**Authors:**
S.Aranganayagi,
K.Thangavel

**Abstract:**

K-Modes is an extension of K-Means clustering algorithm, developed to cluster the categorical data, where the mean is replaced by the mode. The similarity measure proposed by Huang is the simple matching or mismatching measure. Weight of attribute values contribute much in clustering; thus in this paper we propose a new weighted dissimilarity measure for K-Modes, based on the ratio of frequency of attribute values in the cluster and in the data set. The new weighted measure is experimented with the data sets obtained from the UCI data repository. The results are compared with K-Modes and K-representative, which show that the new measure generates clusters with high purity.

**Keywords:**
Clustering,
categorical data,
K-Modes,
weighted dissimilarity
measure

##### 671 On Strong(Weak) Domination in Fuzzy Graphs

**Authors:**
C.Natarajan,
S.K.Ayyaswamy

**Abstract:**

Let G be a fuzzy graph. Then D Ôèå V is said to be a strong (weak) fuzzy dominating set of G if every vertex v ∈ V -D is strongly (weakly) dominated by some vertex u in D. We denote a strong (weak) fuzzy dominating set by sfd-set (wfd-set). The minimum scalar cardinality of a sfd-set (wfd-set) is called the strong (weak) fuzzy domination number of G and it is denoted by γsf (G)γwf (G). In this paper we introduce the concept of strong (weak) domination in fuzzy graphs and obtain some interesting results for this new parameter in fuzzy graphs.

**Keywords:**
Fuzzy graphs,
fuzzy domination,
strong (weak) fuzzy domination number.

##### 670 Video Quality Control Using a ROI and Two- Component Weighted Metrics

**Authors:**
Petra Heribanová,
Jaroslav Polec,
Michal Martinovič

**Abstract:**

In this paper we propose a new content-weighted method for full reference (FR) video quality control using a region of interest (ROI) and wherein two-component weighted metrics for Deaf People Video Communication. In our approach, an image is partitioned into region of interest and into region "dry-as-dust", then region of interest is partitioned into two parts: edges and background (smooth regions), while the another methods (metrics) combined and weighted three or more parts as edges, edges errors, texture, smooth regions, blur, block distance etc. as we proposed. Using another idea that different image regions from deaf people video communication have different perceptual significance relative to quality. Intensity edges certainly contain considerable image information and are perceptually significant.

**Keywords:**
Video quality assessment,
weighted MSE.

##### 669 Total Chromatic Number of Δ-Claw-Free 3-Degenerated Graphs

**Authors:**
Wongsakorn Charoenpanitseri

**Abstract:**

**Keywords:**
Total colorings,
the total chromatic number,
3-degenerated.

##### 668 Attribute Weighted Class Complexity: A New Metric for Measuring Cognitive Complexity of OO Systems

**Authors:**
Dr. L. Arockiam,
A. Aloysius

**Abstract:**

**Keywords:**
Software Complexity,
Attribute Weighted Class Complexity,
Weighted Class Complexity,
Data Type

##### 667 Using the OWA Operator in the Minkowski Distance

**Authors:**
José M. Merigó,
Anna M. Gil-Lafuente

**Abstract:**

**Keywords:**
Aggregation operators,
Minkowski distance,
OWA
operators,
Selection of strategies.

##### 666 Exploring Counting Methods for the Vertices of Certain Polyhedra with Uncertainties

**Authors:**
Sammani Danwawu Abdullahi

**Abstract:**

*fpras*) of counting the vertices of some special classes of polyhedra associated with Down-Sets, Independent Sets, 2-Knapsack problems and

*2 x n*transportation problems are presented together with some discovered open problems.

**Keywords:**
Approximation,
counting with uncertainties,
mathematical programming,
optimization,
vertex enumeration.

##### 665 Variogram Fitting Based on the Wilcoxon Norm

**Authors:**
Hazem Al-Mofleh,
John Daniels,
Joseph McKean

**Abstract:**

**Keywords:**
Non-Linear Wilcoxon,
robust estimation,
Variogram
estimation.