1,720,978 research outputs found
The degree-preserving spanning tree problem in strongly chordal and directed path graphs
No full text
Inhibition of allergen-induced airway inflammation and hyperreactivity by recombinant lactic-acid bacteria
No full textLocally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
No full textWork of breathing and respiratory drive in obesity
No full textObesity, particularly severe central obesity, affects respiratory physiology both at rest and during exercise. Reductions in expiratory reserve volume, functional residual capacity, respiratory system compliance and impaired respiratory system mechanics produce a restrictive ventilatory defect. Low functional residual capacity and reductions in expiratory reserve volume increase the risk of expiratory flow limitation and airway closure during quiet breathing. Consequently, obesity may cause expiratory flow limitation and the development of intrinsic positive end expiratory pressure, especially in the supine position. This increases the work of breathing by imposing a threshold load on the respiratory muscles leading to dyspnoea. Marked reductions in expiratory reserve volume may lead to ventilation distribution abnormalities, with closure of airways in the dependent zones of the lungs, inducing ventilation perfusion mismatch and gas exchange abnormalities. Obesity may also impair upper airway mechanical function and neuromuscular strength, and increase oxygen consumption, which in turn, increase the work of breathing and impair ventilatory drive. The combination of ventilatory impairment, excess CO2 production and reduced ventilatory drive predisposes obese individuals to obesity hypoventilation syndrome
Spanning Tree Problems on Graph Classes
No full text生成樹 (spanning tree) 問題在計算機科學上，不僅是演算法領域的一個重要課題，同時也具有許多實務上的應用。例如通訊網路設計、圖形編碼以及傳輸路徑設計。根據不同的應用需求，所產生的生成樹問題也不同。最為人所知的生成樹問題為最小成本生成樹 (minimum cost spanning tree) 以及最短路徑生成樹 (shortest path tree)。這兩個問題都是古典的生成樹問題，且均可在多項式時間內被解決。然而，並不是所有生成樹問題都是容易解決的。例如斯坦納最小成本樹(Steiner minimal tree) 以及最多葉生成樹 (maximum leaf spanning tree) 都是屬於NP-complete的問題。
我的論文─各種圖類上的生成樹問題，主要是研究局部連通生成樹 (locally connected spanning tree) 與度保留生成樹 (degree-preserving spanning tree)。這兩個生成樹問題已經被證明是 NP-complete。我的研究主要是在 directed path graph，strongly chordal graph 與 circular-arc graph 這三種不同的圖類 (graph class) 上設計多項式時間演算法。
局部連通生成樹問題是要在圖上找一棵生成樹，使得每一個點位於樹上的鄰居在原圖上所形成的誘導子圖 (induced subgraph) 會是連通的。在給定 strong elimination order 的情況下，我們在 strongly chordal graph 上提出一個 O(m+n)-time 演算法。在給定 intersection model 的情況下，我們在 circular-arc graph 上設計出一個 O(n)-time 演算法。以上這兩個演算法均可測定圖是否含有局部連通生成樹。如果有，我們將產生此局部連通生成樹。
度保留生成樹這一個問題是要在圖上找一棵生成樹具有最多的度保留點 (degree-preserving vertex)。對於一個點而言，如果它在圖上的鄰居與它在生成樹上的鄰居相同，則我們稱這個點具有度保留的性質。在給定 strong elimination order 及 tail order 的情況下，我們在 strongly chordal graph 及 directed path graph上分別提出 O(m α(m,n))-time 及 O(m+n)-time 演算法。在 intersection model 給定的情況下，我們在 circular-arc graph 上設計出 O(n^2)-time 演算法。以上這三個演算法均會產生度保留生成樹。A spanning subgraph of a graph G is a subgraph containing all vertices of G. A spanning tree of G is a spanning subgraph of G that is a tree. Spanning trees are not only fundamental in algorithmic graph theory but also practically important in many applications such as communication networks, messages encoding and routing algorithm. Based on different criteria on spanning trees, there are different types of spanning trees. The most famous spanning tree problems are the minimum cost spanning tree problem and the shortest path tree problem. Both problems are solvable in polynomial time. On the other hand, some spanning tree problems are not easy to be solved. For example, the Steiner minimal tree problem and the maximum leaf spanning tree problem are NP-complete.
In this dissertation, we study the problems of finding locally connected spanning trees and degree-preserving spanning trees. Both problems have been proven to be NP-complete on general graphs. We design polynomial-time algorithms for these two problems on some graph classes such as directed path graphs, strongly chordal graphs and circular-arc graphs.
A locally connected spanning tree of a graph G is a spanning tree T such that the set of all neighbors of v in T induces a connected subgraph of G for every vertex v of G. Given a strong elimination order of a strongly chordal graph, we propose an O(m+n)-time algorithm for determining whether the graph contains a locally connected spanning tree and producing it if it exists. Further, given an intersection model of a circular-arc graph, an O(n)-time algorithm for finding locally connected spanning trees on circular-arc graphs are proposed.
A vertex v of G is a degree-preserving vertex if its degree in T is the same as in G. The degree-preserving spanning tree problem is to find a spanning tree T of a connected graph G such that the number of degree-preserving vertices is maximum. Given a strong elimination order of a strongly chordal graph, we show an O(m α(m, n))-time algorithm on strongly chordal graphs, where α is the inverse of Ackermann's function. Moreover, given a tail order of a directed path graph, an O(m+n)-time algorithm for the degree-preserving spanning tree problem on directed path graphs is proposed. Further, given an intersection model of a circular-arc graph, we show an algorithm on circular-arc graphs that can be completed in O(n^2) time.1 Introduction
1.1 Spanning tree problems. . 2
1.1.1 Locally connected spanning trees. . 2
1.1.2 Degree-preserving spanning trees. . 4
1.2 Graph classes. . 5
1.2.1 Interval graphs and directed path graphs. . 6
1.2.2 Chordal graphs and strongly chordal graphs. . 7
1.2.3 Circular-arc graphs. . 8
1.2.4 Graph classes relationships. . 10
1.3 Previous results. . 11
1.3.1 Locally connected spanning trees. . 11
1.3.2 Degree-preserving spanning trees. . 12
1.4 Thesis organization. . 12
2 Locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs. . 15
2.1 An O(m+n)-time algorithm for strongly chordal graphs. . 16
2.2 An O(m+n)-time algorithm for proper circular-arc graphs. . 20
3 Locally connected spanning trees on circular-arc graphs. . 27
3.1 An algorithm for interval graphs. . 28
3.2 No vertex v with d(v)=2. . 33
3.3 Three vertices v with d(v)=2. . 39
3.4 Two vertices v with d(v)=2. . 43
3.5 One vertex v with d(v)=2. . 49
3.5.1 A vertex v_p(γ) in G. . 50
3.5.2 No vertex v_p(γ) in G. . 54
4 Degree-preserving spanning trees on graphs. . 62
4.1 An O(mα(m,n))-time algorithm for strongly chordal graphs. . 63
4.2 An O(m + n)-time algorithm for directed path graphs. . 67
4.3 An O(n2)-time algorithm for circular-arc graphs. . 71
5 Discussion and conclusion. . 78
5.1 Contribution. . 78
5.2 Future work. . 8
Supplemental_Table_20180618_Final – Supplemental material for Choices for long-term hypertensive control in patients after first-ever hemorrhagic stroke: a nationwide cohort study
No full textSupplemental material, Supplemental_Table_20180618_Final for Choices for long-term hypertensive control in patients after first-ever hemorrhagic stroke: a nationwide cohort study by Chi-Hung Liu, Yu-Sheng Lin, Ching-Chi Chi, Chia-Wei Liou, Jiann-Der Lee, Tsung-I Peng and Tsong-Hai Lee in Therapeutic Advances in Neurological Disorders</p
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
