155 research outputs found
Peranan Kantor Urusan Agama dalam Membangun Keluarga Sakinah di Keluran Boting Kecamatan Wara Kota Palopo
No full textHasil penelitian menunjukan bahwa: 1. Kondisi masyarakat Kelurahan Boting
Kecamatan Wara sangat rukun, meskipun ada perbedaan agama tapi mereka tetap
menghormati satu sama lain. 2. Upaya-upaya yang dilakukan Kantor Urusan Agama
dalam membangun keluarga sakinah yaitu: 1) pembinaan Pranikah melalui
program usia nikah dan suscatin, 2) Penyuluhan rutin kepada masyarakat, 3)
Pembinaan aspek keagamaan melalui majelis taklim dan jumat ibadah
Implikasi penelitian ini adalah Melihat kondisi SDM khususnya di Kantor
Urusan Agama Kelurahan Boting Kecamatan Wara Kota Palopo, perlu diadakan
pembekalan yang lebih dalam dan diadakan penambahan SDM yang lebih
profesional sehingga dapat terlaksana program pembinaan keluarga sakinah, Perlu
diadakan pegawai yang berasal dari jurusan Bimbingan dan Penyuluhan Islam, Perlu
adanya peningkatan kerjasama antara Kantor Urusan Agama dengan Kantor
Pengadilan Agama setempat dan untuk pasangan suami-istri, jangan pernah merasa
malu untuk datang berkonsultasi guna memperoleh nasehat dari konsultan
pernikahan sebagai upaya mencari jalan keluar dalam mengatasi permasalahanpermasalahan
yang dihadapi dalam kehidupan rumah tangga
Four-Searchable Biconnected Outerplanar Graphs
No full textThis paper deals with constructing obstruction sets for two subclasses of 4-searchable graphs. We first characterize the 4-searchable biconnected outerplanar graphs by listing all graphs that cannot be their minors; we then give a constructive characterization of such graphs. We also characterize the 4-searchable biconnected generalized wheel graphs by listing all graphs that cannot be their minors. Crown Copyright (C) 2021 Published by Elsevier B.V. All rights reserved.EU Marie Curie International Reintegration, European Union [PIRG07/GA/2010/268322]; Kadir Has University BAP, Turkey [2011-BAP-07]; NSERC, Canada [RGPIN-2018-06800]Oznur Yasar Diner is partially supported by the EU Marie Curie International Reintegration, European Union Grant [grant number PIRG07/GA/2010/268322] and by Kadir Has University BAP, Turkey [grant number 2011-BAP-07]. Danny Dyer is partially supported by NSERC, Canada. Boting Yang is partially supported by an NSERC, Canada Discovery Research Grant [grant number RGPIN-2018-06800]
Genomic Scaffold Filling Revisited
No full textThe genomic scaffold filling problem has attracted a lot of attention recently. The problem is on filling an incomplete sequence (scaffold) I into I', with respect to a complete reference genome G, such that the number of adjacencies between G and I' is maximized. The problem is NP-complete and APX-hard, and admits a 1.2-approximation. However, the sequence input I is not quite practical and does not fit most of the real datasets (where a scaffold is more often given as a list of contigs). In this paper, we revisit the genomic scaffold filling problem by considering this important case when, (1) a scaffold S is given, the missing genes X = c(G) - c(S) can only be inserted in between the contigs, and the objective is to maximize the number of adjacencies between G and the filled S' and (2) a scaffold S is given, a subset of the missing genes X' subset X = c(G) - c(S) can only be inserted in between the contigs, and the objective is still to maximize the number of adjacencies between G and the filled S''. For problem (1), we present a simple NP-completeness proof, we then present a factor-2 greedy approximation algorithm, and finally we show that the problem is FPT when each gene appears at most d times in G. For problem (2), we prove that the problem is W[1]-hard and then we present a factor-2 FPT-approximation for the case when each gene appears at most d times in G
Learning hypertrees with shortest path queries
No full textA Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Science, University of Regina. vii, 56 p.One branch of computational learning theory focuses on algorithms for learning
discrete structured objects from queries. In this context, we consider the problem of
learning a labeled hypergraph from a given family of hypergraphs using shortest path
(SP) queries. An SP query specifies two vertices and asks for their distance in the
target hypergraph. For various classes H of hypertrees, we present bounds on the
number of queries required to learn an unknown hypertree from H. Matching upper
and lower asymptotic bounds are presented for learning hyperpaths and hyperstars.
Moreover, inspired by Hein’s algorithm for learning evolutionary trees with bounded
vertex degrees, we develop an efficient algorithm for learning any hypertree. The
query complexity of the algorithm is bounded from above by a function linear in the
edge degree. As part of this research, we also introduce the notion of bag graph,
which is a new way to generalize a graph, and provide an efficient algorithm for
learning certain bag trees with SP queries. The query complexity of the algorithm
for learning bag trees is bounded from above by a function linear in the bag degree.
This algorithm allows us to carry over ideas from Hein’s algorithm for learning trees
to our task of learning hypertrees.Studentye
Fast edge searching and fast searching on graphs
No full textAbstractGiven a graph G=(V,E) in which a fugitive hides on vertices or along edges, graph searching problems are usually to find the minimum number of searchers required to capture the fugitive. In this paper, we consider the problem of finding the minimum number of steps to capture the fugitive. We introduce the fast edge searching problem in the edge search model, which is the problem of finding the minimum number of steps (called the fast edge-search time) to capture the fugitive. We establish relations between the fast edge searching and the fast searching that is the problem of finding the minimum number of searchers to capture the fugitive in the fast search model. While the family of graphs whose fast search number is at most k is not minor-closed for any positive integer k≥2, we show that the family of graphs whose fast edge-search time is at most k is minor-closed. We establish relations between the fast (fast edge) searching and the node searching. These relations allow us to transform the problem of computing node search numbers to the problem of computing fast edge-search numbers or fast search numbers. Using these relations, we prove that the problem of deciding, given a graph G and an integer k, whether the fast (edge-)search number of G is less than or equal to k is NP-complete; and it remains NP-complete for Eulerian graphs. We also prove that the problem of determining whether the fast (edge-)search number of G is half of the number of odd vertices in G is NP-complete; and it remains NP-complete for planar graphs with maximum degree 4. We present a linear time approximation algorithm for the fast edge-search time that always delivers solutions of at most (1+|V|−1|E|+1) times the optimal value. This algorithm also gives us a tight upper bound on the fast search number of graphs. We also show a lower bound on the fast search number using the minimum degree and the number of odd vertices
REVO: A flexible, volumetric approach to mesh construction
No full textA Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Science, University of Regina. xi, 121 p.Meshes are used in a variety of applications to specify the three dimensional (3D)
shapes of objects in simulated scenes. For example, a mesh can be used as an animal
in an animation movie, a soldier in a video game, or a bulldozer in a simulation
application. A straightforward way of creating a mesh is to modify an existing mesh.
Although several mesh modi cation algorithms exist, there is a need for an algorithm
that constructs a mesh from any combination of existing meshes and simple geometric
shapes (called primitives) according to a list of user commands. When visualized, the
resulting mesh should have a smooth (i.e. not blocky) surface.
We propose the Revo method for constructing meshes from any combination of
existing meshes or primitives according to user commands. The commands required
to construct a speci c 3D mesh should be determined by an artist. First, the Revo
method generates a volumetric representation of each input mesh or primitive. To do
so, for each input mesh, it imposes a 3D grid called a volumetric grid on the portion
of the 3D world that contains the mesh. Revo may apply some transformations to an
input mesh to ensure that it is completely enclosed by the volumetric grid. A distance
eld is used to approximate the input mesh in the volumetric grid. Similarly, each
required primitive is constructed in a volumetric grid to yield a distance eld. A
series of distance-based operations, such as union, intersection, and subtraction, are
used to combine the distance elds according to the user commands. Finally, Revo
extracts the implicit surface from the resulting distance eld and constructs a mesh.
We analyzed the Revo method theoretically and empirically. Our analysis shows that the size of the volumetric grid a ects the accuracy of the volumetric data, the
complexity of the generated mesh, and the performance of the algorithm. Using a
larger volumetric grid results in more accurate volumetric data. However, it makes
the process slower and the generated mesh more complex. The characteristics of the
input meshes, such as the number of triangles, also a ect the performance of Revo.
For a highly detailed input mesh, the generated mesh has fewer triangles than the
input mesh because the output mesh has less detail than the input mesh. Also, the
processing time and theStudentye
Parameterized algorithms for generalized domination
No full textWe study the parameterized complexity of a generalization of Dominating Set problem, namely, the Vector Dominating Set problem. Here, given an undirected graph G∈=∈(V,E), with V∈=∈{v 1, ∈⋯∈, v n }, a vector and an integer parameter k, the goal is to determine whether there exists a subset D of at most k vertices such that for every vertex v∈ ∈V ≥ D, at least l(v) of its neighbors are in D. This problem encompasses the well studied problems - Vertex Cover (when l(v)∈=∈d(v) for all v∈ ∈V, where d(v) is the degree of vertex v) and Dominating Set (when l(v)∈=∈1 for all v∈ ∈V). While Vertex Cover is known to be fixed parameter tractable, Dominating Set is known to be W[2]-complete. In this paper, we identify vectors based on several measures for which this generalized problem is fixed parameter tractable and W-hard. We also show that the Vector Dominating Set is fixed parameter tractable for graphs of bounded degeneracy and for graphs excluding cycles of length four
- …
