154 research outputs found
Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size
No full textThe (Weighted) Subset Feedback Vertex Set problem is a generalization of the classical Feedback Vertex Set problem and asks for a vertex set of minimum (weight) size that intersects all cycles containing a vertex of a predescribed set of vertices. Although the two problems exhibit different computational complexity on split graphs, no similar characterization is known on other classes of graphs. Towards the understanding of the complexity difference between the two problems, it is natural to study the importance of a structural graph parameter. Here we consider graphs of bounded independent set number for which it is known that Weighted Feedback Vertex Set can be solved in polynomial time. We provide a dichotomy result with respect to the size of a maximum independent set. In particular we show that Weighted Subset Feedback Vertex Set can be solved in polynomial time for graphs of independent set number at most three, whereas we prove that the problem remains NP-hard for graphs of independent set number four. Moreover, we show that the (unweighted) Subset Feedback Vertex Set problem can be solved in polynomial time on graphs of bounded independent set number by giving an algorithm with running time n^{O(d)}, where d is the size of a maximum independent set of the input graph. To complement our results, we demonstrate how our ideas can be extended to other terminal set problems on graphs of bounded independent set size. Based on our findings for Subset Feedback Vertex Set, we settle the complexity of Node Multiway Cut, a terminal set problem that asks for a vertex set of minimum size that intersects all paths connecting any two terminals, as well as its variants where nodes are weighted and/or the terminals are deletable, for every value of the given independent set number
Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs
No full textIn social networks the Strong Triadic Closure is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which the problem is solvable. We show that the problem admits a polynomial-time algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete
Cluster Deletion on Interval Graphs and Split Related Graphs
No full textIn the Cluster Deletion problem the goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on (P_5-free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deletion on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of the algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of P_5-free chordal graphs. Although the later result arises from the already-known reduction for P_5-free chordal graphs, we give an alternative proof showing an interesting connection between edge-weighted and vertex-weighted variations of the problem. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs
Ep025 about writing children's book, and teaching children about history and folklore in fun and exciting ways.
No full textCharis Cotter is an award-winning children’s writer, actor and storyteller who has worked extensively in schools telling Newfoundland ghost stories and encouraging students to collect local ghost stories from their communities. In 2013 she published The Ghosts of Baccalieu, a book of traditional ghost stories by students from Tricon Elementary in Bay de Verde. Her latest storytelling presentation, The Ghosts of Grates Cove, is an hour of ghost stories from one of the most haunted places in Newfoundland, Conception Bay North. We discuss Charis’ work as an author, how she teaches children facts through games and fun, school programs, and ghost stories
Parameterized Aspects of Strong Subgraph Closure
No full textMotivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the Strong F-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In Strong F-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to destroy that strong copy of F in G.
We study Strong F-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when F =P_3. In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization k - mu(G), where mu(G) is the maximum matching size of G. We conclude with some results on the parameterization of Strong F-closure by the number of edges of G that are not selected as strong
Dante's Beatrice ("dolce amica") and Petrarch's Laura ("dolce nemica") : "charis" and poetry
No full textTematem artykułu jest analiza dwóch najsłynniejszych postaci kobiecych w literaturze włoskiej, Beatrycze i Laury i roli, jaką ich charis, rozumiana jako uroda, wdzięk, ale także piękno wewnętrzne, czy nawet łaska w – przypadku Beatrycze – oraz pełen sprzeczności obraz wewnętrzny Laury rzutujący na stosunek poety do niej, odegrały w twórczości Dantego i Petrarki i w pojmowaniu przez nich celów poezji. Przedmiotem zainteresowania nie są historyczne cechy osobowości Beatrycze i Laury (nie wiemy nawet, czy ta ostania istniała naprawdę), a jedynie ich wyobrażenie literackie, obecne w różnych dziełach obu twórców. W analizie o charakterze interpretacyjnym autorka artykułu odwołuje się do "Vita Nuova" i "Divina Commedia" Dantego oraz do "Secretum" i "Rerum vulgarium fragmenta" Petrarki. Auto-dekonstrukcji miłosnej iluzji młodszego poety zostaje przeciwstawiony ewolucyjny wymiar miłości Alighierego: oba te zjawiska decydująco wpłynęły na rozwój ich twórczych osobowości.The article contains an analysis of two most famous female characters in Italian literature: Beatrice and Laura and the role which their charis performed in the oeuvre of Dante and Petrarch. The author also analyses the poets’ understanding of the functions of poetry. Charis was described as beauty, grace, but also internal beauty, or even mercy – as in the case of Beatrice, and an internal image of Laura full of contradictions which affected the relation of the poet to her. The object of the research is not the historical attributes of Beatrice and Laura (we even do not know whether the latter actually existed), but their literary representations existing in different works of both authors. In the interpretative analysis the author refers to "Vita Nuova" and "Divina Commedia" by Dante and "Secretum" and "Rerum vulgarium fragmenta" by Petrarch. The auto-destructive amorous illusion of the younger poet has
been juxtaposed with the evolutionary dimension of affection by Alighieri: both phenomena decisively influenced the development of their artistic work
Implementation of a class-wide intervention to teach behavioral expectations in Head Start
No full textChildren and teachers were recruited from two Head Start programs in a Midwestern city to participate in this study focused on behavioral expectations. Using a multiple probe design across four classrooms, the impact of scripted stories, role play, and prompts was examined. Teachers were trained on how to implement effective strategies to teach behavioral expectations to young children. Although a functional relation was not established, teachers implemented the evidence-based strategies with high fidelity which resulted in adherence to behavioral expectations for two child participants.Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2017-12-01The student, Charis Price, accepted the attached license on 2015-11-19 at 16:13.The student, Charis Price, submitted this Dissertation for approval on 2015-11-19 at 16:36.This Dissertation was approved for publication on 2015-11-30 at 11:13.DSpace SAF Submission Ingestion Package generated from Vireo submission #8812 on 2016-03-02 at 14:06:00Made available in DSpace on 2016-03-02T20:23:34Z (GMT). No. of bitstreams: 2
PRICE-DISSERTATION-2015.pdf: 1328030 bytes, checksum: 85367f1655a900257f6686b3a1fcdb87 (MD5)
LICENSE.txt: 4209 bytes, checksum: 099f45d5c366151995593f7e026807e9 (MD5)
Previous issue date: 2015-11-30Embargo set by: Seth Robbins for item 91320
Lift date: 2018-03-02T20:24:31Z
Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD systemU of I Only Restriction Lifted for Item 91320 on 2018-03-03T10:15:18Z
Restricted vertex multicut on permutation graphs
No full textAbstract Given an undirected graph and pairs of terminals the Restricted Vertex Multicut problem asks for a minimum set of nonterminal vertices whose removal disconnects each pair of terminals. The problem is known to be NP-complete for trees and polynomial-time solvable for interval graphs. In this paper we give a polynomial-time algorithm for the problem on permutation graphs. Furthermore we show that the problem remains NP-complete on split graphs whereas it becomes polynomial-time solvable for the class of co-bipartite graphs
Restricted vertex multicut on permutation graphs
No full textAbstractGiven an undirected graph and pairs of terminals the Restricted Vertex Multicut problem asks for a minimum set of nonterminal vertices whose removal disconnects each pair of terminals. The problem is known to be NP-complete for trees and polynomial-time solvable for interval graphs. In this paper we give a polynomial-time algorithm for the problem on permutation graphs. Furthermore we show that the problem remains NP-complete on split graphs whereas it becomes polynomial-time solvable for the class of co-bipartite graphs
Combination of Pretreatment with White Rot Fungi and Modification of Primary and Secondary Cell Walls Improves Saccharification
No full textPlant cell walls have protective and structural functions conferring resistance to degradation. The lignin and hemicellulose network surrounding the cellulose microfibrils is insoluble unless subjected to harsh treatments. As lignin, pectin and xylan are effective barriers to cellulose extraction and hydrolysis, reducing their presence in cell walls improves saccharification. Microorganisms that can depolymerise lignin are of extreme interest to the biofuel industry. White rot fungi can be effective in pretreatment of lignocellulosic biomass prior to saccharification. Here, we show the cumulative effects of pretreating biomass with two white rot fungi, Phanerochaete chrysosporium and Trametes cingulata, on tobacco lines with reduced lignin or xylan, caused by suppression of the CINNAMOYL-CoA REDUCTASE, CINNAMATE-4-HYDROXYLASE, TOBACCO PEROXIDASE 60 or UDP-GLUCURONATE DECARBOXYLASE and on Arabidopsis thaliana with reduced de-esterified homogalacturonan content, obtained by overexpressing a pectin methyl esterase inhibitor or constitutively expressing the Aspergillus nigerPOLYGALACTURONASE II gene. Tests were extended to fresh material from an Arabidopsis mutant for a cell wall peroxidase. We demonstrate that fungal pretreatment is a reliable method of improving cellulose accessibility in biofuel feedstocks, fresh material and cell wall residues from different plants. These results contribute to the understanding of the consequences of primary and secondary cell wall perturbations on lignocellulosic biomass accessibility to white rot fungi and on saccharification yield. A comparison of the effects of P. chrysosporium and T. cingulata on tobacco saccharification also highlights the limitation of current knowledge in this research field and the necessity to systematically test culture conditions to avoid generalisations. © 2014 The Author(s)
- …
