**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**1871

# Search results for: vertex support

##### 1871 Optimization of Unweighted Minimum Vertex Cover

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

**Abstract:**

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

##### 1870 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.

##### 1869 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.

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

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

**Abstract:**

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

##### 1867 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

##### 1866 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.

##### 1865 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.

##### 1864 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.

##### 1863 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.

##### 1862 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.

##### 1861 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.

##### 1860 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.

##### 1859 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.

##### 1858 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.

##### 1857 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.

##### 1856 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.

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

**Authors:**
Wongsakorn Charoenpanitseri

**Abstract:**

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

##### 1854 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.

##### 1853 Skolem Sequences and Erdosian Labellings of m Paths with 2 and 3 Vertices

**Authors:**
H. V. Chen

**Abstract:**

**Keywords:**
c-Erdösian,
Skolem sequences,
magic labelling

##### 1852 Investigation of Stability of Functionally Graded Material when Encountering Periodic Loading

**Authors:**
M. Amiri

**Abstract:**

In this work, functionally graded materials (FGMs), subjected to loading, which varies with time has been studied. The material properties of FGM are changing through the thickness of material as power law distribution. The conical shells have been chosen for this study so in the first step capability equations for FGM have been obtained. With Galerkin method, these equations have been replaced with time dependant differential equations with variable coefficient. These equations have solved for different initial conditions with variation methods. Important parameters in loading conditions are semi-vertex angle, external pressure and material properties. Results validation has been done by comparison between with those in previous studies of other researchers.

**Keywords:**
Impulsive semi-vertex angle,
loading,
functionally graded materials,
composite material.

##### 1851 Cycle Embedding in Folded Hypercubes with More Faulty Elements

**Authors:**
Wen-Yin Huang,
Jia-Jie Liu,
Jou-Ming Chang

**Abstract:**

Faults in a network may take various forms such as hardware/software errors, vertex/edge faults, etc. Folded hypercube is a well-known variation of the hypercube structure and can be constructed from a hypercube by adding a link to every pair of nodes with complementary addresses. Let FFv (respectively, FFe) be the set of faulty nodes (respectively, faulty links) in an n-dimensional folded hypercube FQn. Hsieh et al. have shown that FQn - FFv - FFe for n ≥ 3 contains a fault-free cycle of length at least 2n -2|FFv|, under the constraints that (1) |FFv| + |FFe| ≤ 2n - 4 and (2) every node in FQn is incident to at least two fault-free links. In this paper, we further consider the constraints |FFv| + |FFe| ≤ 2n - 3. We prove that FQn - FFv - FFe for n ≥ 5 still has a fault-free cycle of length at least 2n - 2|FFv|, under the constraints : (1) |FFv| + |FFe| ≤ 2n - 3, (2) |FFe| ≥ n + 2, and (3) every vertex is still incident with at least two links.

**Keywords:**
Folded hypercubes,
interconnection networks,
cycle embedding,
faulty elements.

##### 1850 N-Sun Decomposition of Complete Graphs and Complete Bipartite Graphs

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

**Abstract:**

**Keywords:**
Hamilton cycle,
n-sun decomposition,
perfectmatching,
spanning tree.

##### 1849 3D Oil Reservoir Visualisation Using Octree Compression Techniques Utilising Logical Grid Co-Ordinates

**Authors:**
S. Mulholland

**Abstract:**

Octree compression techniques have been used for several years for compressing large three dimensional data sets into homogeneous regions. This compression technique is ideally suited to datasets which have similar values in clusters. Oil engineers represent reservoirs as a three dimensional grid where hydrocarbons occur naturally in clusters. This research looks at the efficiency of storing these grids using octree compression techniques where grid cells are broken into active and inactive regions. Initial experiments yielded high compression ratios as only active leaf nodes and their ancestor, header nodes are stored as a bitstream to file on disk. Savings in computational time and memory were possible at decompression, as only active leaf nodes are sent to the graphics card eliminating the need of reconstructing the original matrix. This results in a more compact vertex table, which can be loaded into the graphics card quicker and generating shorter refresh delay times.

**Keywords:**
3D visualisation,
compressed vertex tables,
octree compression techniques,
oil reservoir grids.

##### 1848 An Efficient 3D Animation Data Reduction Using Frame Removal

**Authors:**
Jinsuk Yang,
Choongjae Joo,
Kyoungsu Oh

**Abstract:**

Existing methods in which the animation data of all frames are stored and reproduced as with vertex animation cannot be used in mobile device environments because these methods use large amounts of the memory. So 3D animation data reduction methods aimed at solving this problem have been extensively studied thus far and we propose a new method as follows. First, we find and remove frames in which motion changes are small out of all animation frames and store only the animation data of remaining frames (involving large motion changes). When playing the animation, the removed frame areas are reconstructed using the interpolation of the remaining frames. Our key contribution is to calculate the accelerations of the joints of individual frames and the standard deviations of the accelerations using the information of joint locations in the relevant 3D model in order to find and delete frames in which motion changes are small. Our methods can reduce data sizes by approximately 50% or more while providing quality which is not much lower compared to original animations. Therefore, our method is expected to be usefully used in mobile device environments or other environments in which memory sizes are limited.

**Keywords:**
Data Reduction,
Interpolation,
Vertex Animation,
3D
Animation.

##### 1847 Modeling Aeration of Sharp Crested Weirs by Using Support Vector Machines

**Authors:**
Arun Goel

**Abstract:**

**Keywords:**
Air entrainment rate,
dissolved oxygen,
regression,
SVM,
weir.

##### 1846 Enhanced Frame-based Video Coding to Support Content-based Functionalities

**Authors:**
Prabhudev Hosur,
Rolando Carrasco

**Abstract:**

This paper presents the enhanced frame-based video coding scheme. The input source video to the enhanced frame-based video encoder consists of a rectangular-size video and shapes of arbitrarily-shaped objects on video frames. The rectangular frame texture is encoded by the conventional frame-based coding technique and the video object-s shape is encoded using the contour-based vertex coding. It is possible to achieve several useful content-based functionalities by utilizing the shape information in the bitstream at the cost of a very small overhead to the bitrate.

**Keywords:**
Video coding,
content-based,
hyper video,
interactivity,
shape coding,
polygon.

##### 1845 The Spanning Laceability of k-ary n-cubes when k is Even

**Authors:**
Yuan-Kang Shih,
Shu-Li Chang,
Shin-Shin Kao

**Abstract:**

**Keywords:**
container,
Hamiltonian,
k-ary n-cube,
m*-connected.

##### 1844 Geometry Design Supported by Minimizing and Visualizing Collision in Dynamic Packing

**Authors:**
Johan Segeborn,
Johan S. Carlson,
Robert Bohlin,
Rikard Söderberg

**Abstract:**

**Keywords:**
Dynamic packing,
path planning,
shrinking.

##### 1843 Javanese Adolescents- Future Orientation and Support for its Effort: An Indigenous Psychological Analysis

**Authors:**
Niken Rarasati,
Moh. A. Hakim,
Kwartarini W. Yuniarti

**Abstract:**

**Keywords:**
Affection support,
future orientation,
indigenous
psychology,
Javanese adolescent

##### 1842 Integrated Social Support through Social Networks to Enhance the Quality of Life of Metastatic Breast Cancer Patients

**Authors:**
B. Thanasansomboon,
S. Choemprayong,
N. Parinyanitikul,
U. Tanlamai

**Abstract:**

**Keywords:**
Social support,
metastatic breast cancer,
quality of life,
social network.