26 research outputs found
On the Kernel and Related Problems in Interval Digraphs
No full textGiven a digraph G, a set X ⊆ V(G) is said to be an absorbing set (resp. dominating set) if every vertex in the graph is either in X or is an in-neighbour (resp. out-neighbour) of a vertex in X. A set S ⊆ V(G) is said to be an independent set if no two vertices in S are adjacent in G. A kernel (resp. solution) of G is an independent and absorbing (resp. dominating) set in G. The problem of deciding if there is a kernel (or solution) in an input digraph is known to be NP-complete. Similarly, the problems of computing a minimum cardinality kernel, absorbing set (or dominating set) and the problems of computing a maximum cardinality kernel, independent set are all known to be NP-hard for general digraphs. We explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph G is an interval digraph if a pair of intervals (S_u,T_u) can be assigned to each vertex u of G such that (u,v) ∈ E(G) if and only if S_u ∩ T_v ≠ ∅. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs - which arise when we require that the two intervals assigned to a vertex have to intersect. We see as our main contribution the identification of the class of reflexive interval digraphs as an important class of digraphs. We show that all the problems mentioned above are efficiently solvable, in most of the cases even linear-time solvable, in the class of reflexive interval digraphs, but are APX-hard on even the very restricted class of interval digraphs called point-point digraphs, where the two intervals assigned to each vertex are required to be degenerate, i.e. they consist of a single point each. The results we obtain improve and generalize several existing algorithms and structural results for reflexive interval digraphs. We also obtain some new results for undirected graphs along the way: (a) We get an O(n(n+m)) time algorithm for computing a minimum cardinality (undirected) independent dominating set in cocomparability graphs, which slightly improves the existing O(n³) time algorithm for the same problem by Kratsch and Stewart; and (b) We show that the Red Blue Dominating Set problem, which is NP-complete even for planar bipartite graphs, is linear-time solvable on interval bigraphs, which is a class of bipartite (undirected) graphs closely related to interval digraphs
APLIKASI ANTRIAN DAN PENGOLAHAN DATA BALITA BERBASIS WEBSITE (STUDI KASUS : POSYANDU ARUM DALU DESA SANGGRAHAN)
No full textPosyandu activities in Sanggrahan Village have been running smoothly and still use the Posyandu Information System (SIP) book as a guideline for implementing activities. The purpose of this study is to build a web-based application to manage information at Posyandu Arum Dalu Sanggrahan Village. In the web-based application, the author also added a queue number so that the time for implementing posyandu activities could be neatly and better arranged. The author hopes that this web-based application can help the performance and facilitate Midwives and Health Cadres of Sanggrahan Village in terms of processing toddler data.Keywords : Posyandu, Information System, Queue Numbe
The sea-land breeze as local wind, the numerical and analytical approach to its modeling
No full textLecture by Giovanni A. Dalu held at the International Center for Theoretical Physics-Trieste on 16-20 May 1988 during the workshop on Modeling of the Atmospheric Flow Field
Analisis Produktivitas Kerja Pada PT. Perkebunan Hutahaean Afdelling II Daludalu Kab. Rokan Hulu Provinsi Riau
No full textThis study was conducted to determine what factors affect the productivity of PT. Hutahaean Afdelling II Plantation Dalu-dalu Kab. Rokan Hulu Prov. Riau. In carrying
out this research the author took the location at PT. Hutahaean Afdelling II Plantation located in Dalu-dalu of Rokan Hulu Regency. Employment productivity indicators used
include work ability, quantity of work, morale, quality of work. This type of research is quantitative descriptive that prioritizes the questionnaire as a data collector and the
data is then used as the main raw material to analyze the objective conditions in the research location. There are six population groups and the sample in this research are
18 employees of pks, 17 office employees, 1 plant staff, 1 warehouse staff, civil engineering staff 2 persons and 1 staff of BPP (TRansportation). Technique purposive
sampling. Types and data sources used in this study are primary data and secondary data. Primary data is data obtained from the research object that includes population
data, questionnaire data, interview data, and other data deemed necessary. Secondary data is data obtained directly from the company where the research is supporting
research analysis such as general description of the company. The results of the four indicators for employee respondents is 51% and included in the category of Good
Enough. The results showed that the company must maintain and continue to increase work productivity in the future
Uniquely Restricted Matchings in Interval Graphs
No full textA matching M in a graph G is said to be uniquely restricted if there is no other matching in G that matches the same set of vertices as M. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic, Hirst, and Lewenstein [Algorithmica, 31 (2001), pp. 139–154]. Our algorithm actually solves the more general problem of computing a maximum cardinality “weak independent set” in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs
On the Kernel and Related Problems in Interval Digraphs
No full textGiven a digraph G, a set X⊆ V(G) is said to be an absorbing set (resp. dominating set) if every vertex in the graph is either in X or is an in-neighbour (resp. out-neighbour) of a vertex in X. A set S⊆ V(G) is said to be an independent set if no two vertices in S are adjacent in G. A kernel (resp. solution) of G is an independent and absorbing (resp. dominating) set in G. The problem of deciding if there is a kernel (or solution) in an input digraph is known to be NP-complete. Similarly, the problems of computing a minimum cardinality dominating set or absorbing set or kernel, and the problems of computing a maximum cardinality independent set or kernel, are all known to be NP-hard for general digraphs. We explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph G is an interval digraph if a pair of intervals (Su, Tu) can be assigned to each vertex u of G such that (u, v) ∈ E(G) if and only if Su∩ Tv≠ ∅. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs—which arise when we require that the two intervals assigned to a vertex have to intersect. We see as our main contribution the identification of the class of reflexive interval digraphs as an important class of digraphs. We show that while the problems mentioned above are NP-complete, and even hard to approximate, on interval digraphs (even on some very restricted subclasses of interval digraphs called point-point digraphs, where the two intervals assigned to each vertex are required to be degenerate), they are all efficiently solvable, in most of the cases linear-time solvable, in the class of reflexive interval digraphs. The results we obtain improve and generalize several existing algorithms and structural results for subclasses of reflexive interval digraphs. In particular, we obtain a vertex ordering characterization of reflexive interval digraphs that implies the existence of an O(n+ m) time algorithm for computing a maximum cardinality independent set in a reflexive interval digraph, improving and generalizing the earlier known O(nm) time algorithm for the same problem for the interval nest digraphs. (Here m denotes the number of edges in the digraph not counting the self-loops.) We also show that reflexive interval digraphs are kernel-perfect and that a kernel in such digraphs can be computed in linear time. This generalizes and improves an earlier result that interval nest digraphs are kernel-perfect and that a kernel can be computed in such digraphs in O(nm) time. The structural characterizations that we show for point-point digraphs, apart from helping us construct the NP-completeness/APX-hardness reductions, imply that these digraphs can be recognized in linear time. We also obtain some new results for undirected graphs along the way: (a) We describe an O(n(n+ m)) time algorithm for computing a minimum cardinality (undirected) independent dominating set in cocomparability graphs, which slightly improves the existing O(n3) time algorithm for the same problem by Kratsch and Stewart; and (b) We show that the Red-Blue Dominating Set problem, which is NP-complete even for planar bipartite graphs, is linear-time solvable on interval bigraphs, which is a class of bipartite (undirected) graphs closely related to interval digraphs
Graph Burning: Bounds and Hardness
No full textGraph burning models the propagation of information within a network as a
stepwise process where at each step, one node becomes informed, and this
information also spreads to all neighbors of previously informed nodes.
Formally, graph burning is defined as follows: For an undirected graph , at
step all vertices in are unburned. At each step , one new
unburned vertex is selected to burn if such a vertex exists. If a vertex is
burned at step , then all its unburned neighbors are burned in step ,
and the process continues until there are no unburned vertices in . The
burning number of a graph , denoted by , is the minimum number of
steps required to burn all the vertices of . The burning number problem asks
whether the burning number of an input graph is at most or not. In this
paper, we study the burning number problem both from an algorithmic and a
structural point of view. The burning number problem is known to be NP-complete
for trees with maximum degree at most three and interval graphs. Here, we prove
that this problem is NP-complete even when restricted to connected cubic graphs
and connected proper interval graphs. The well-known burning number conjecture
asserts that all the vertices of a graph of order can be burned in
steps. In line with this conjecture, upper and lower
bounds of are well-studied for various graph classes. Here, we provide
an improved upper bound for the burning number of connected -free graphs
and show that the bound is tight up to an additive constant . Finally, we
study two variants of the problem, namely edge burning (only edges are burned)
and total burning (both vertices and edges are burned). In particular, we
establish their relationship with the burning number problem and evaluate the
algorithmic complexity of these variants.Comment: 20 pages, 8 figure
Extending some results on the second neighborhood conjecture
No full textIf in a directed graph, v is an out-neighbor of u and w is an out-neighbor of v but not of u, then w is said to be a second out-neighbor of u. A vertex in a directed graph is said to have a large second neighborhood if it has at least as many second out-neighbors as out-neighbors. The Second Neighborhood Conjecture, first stated by Seymour, asserts that there is a vertex having a large second neighborhood in every oriented graph (a directed graph without loops or digons). It is straightforward to see that the conjecture is true for any oriented graph whose underlying undirected graph is bipartite. We extend this to show that the conjecture holds for oriented graphs whose vertex set can be partitioned into an independent set and a 2-degenerate graph. Fisher proved the conjecture for tournaments and later Havet and Thomassé provided a different proof for the same using median orders of tournaments. Havet and Thomassé in fact showed the stronger statement that if a tournament contains no sink, then it contains at least two vertices with large second neighborhoods. Using their techniques, Fidler and Yuster showed that the conjecture remains true for tournaments from which either a matching or a star has been removed. We extend this result to show that the conjecture holds even for tournaments from which both a matching and a star have been removed. This implies that a tournament from which a matching has been removed contains either a sink or two vertices with large second neighborhoods
Erratum to “Systematic versus on-demand early palliative care: A randomised clinical trial assessing quality of care and treatment aggressiveness near the end of life” [Eur J Cancer (2016) 69 (110–118)] (S095980491632487X)(10.1016/j.ejca.2016.10.004)
No full textThe publisher regrets that the collaborators for this paper were not listed as such within the author details of the published paper. The collaborators were published in the Acknowledgements and are as follows: Alberto Farolfi, Silvia Ruscelli, Martina Valgiusti, Sara Pini, Marina Faedi, Department of Medical Oncology, IRST IRCCS, Meldola; Angela Ragazzini, Unit of Biostatistics and Clinical Trials, IRST IRCCS, Meldola; Cristina Pittureri and Elena Amaducci, Palliative Care and Hospice Unit, AUSL Romagna, Cesena; Irene Guglieri, Psychooncology Service, Veneto Institute of Oncology IOV – IRCCS, Padua; Francesca Bergamo, Sara Lonardi, Department of Clinical and Experimental Oncology, Medical Oncology 1, Veneto Institute of Oncology IOV – IRCCS, Padua; Camilla Di Nunzio, Medical Oncology Unit, Oncology–Hematology Department, Guglielmo da Saliceto Hospital, Piacenza; Monica Bosco, Palliative Care Unit, Oncology–Hematology Department, Guglielmo da Saliceto Hospital, Piacenza; Barbara Bocci, Medical Oncology Unit, San Paolo Hospital, Milan; Alfina Bramanti and Chiara Gandini, Oncology Unit, Fondazione IRCCS Policlinico San Matteo, Pavia; Angela Buonadonna, Medical Oncology Unit, Aviano National Cancer Institute, Aviano; Alessandro Comandone, Medical Oncology Unit, Presidio Humanitas Gradenigo, Turin; Sonia Zoccali, Coordinamento Cure Palliative (supported by F.I.L.E., Leniterapia Italian Foundatio), Florence; Maria Simona Pino, Medical Oncology Unit, Oncology Department, S. Maria Annunziata Hospital, Florence; Davide Dalu, Palliative Care Unit, Oncology Department, L. Sacco Hospital, Milan; Pietro Sozzi, Oncology Unit, Ospedale degli Infermi, Ponderano; Alberto Gozza, Medical Oncology, Department of Medicine, E.O. Galliera Hospitals, Genoa; Monica Giordano and Carla Longhi, Oncology Unit, Sant'Anna Hospital, Como; Cristina Autelitano, Palliative Care Unit, Arcispedale S. Maria Nuova – IRCCS, Reggio Emilia; Teresa Gamucci, Oncology Unit, SS Trinità Hospital Sora, ASL Frosinone, Frosinone; Cataldo Mastromauro, Oncology Unit, ULSS 12 Veneziana, Venice; Rodolfo Scognamiglio, Hospice Nazareth, Mestre; Daniela Degiovanni, Palliative Care Unit, Casale Monferrato, ASL Alessandria; Federica Negri, Medical Oncology Unit, Istituti Ospitalieri, Cremona; Augusto Caraceni, Palliative Care, Pain Therapy and Rehabilitation Department, Fondazione IRCCS Istituto Nazionale dei Tumori, Milan; and Luigi Montanari, Palliative Care Unit Ravenna, AUSL Romagna, Italy. The publisher would like to apologise for any inconvenience caused
