Dissertations / Theses on the topic 'Chordal graph'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 41 dissertations / theses for your research on the topic 'Chordal graph.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Alzaidi, Esraa Raheem. "EXPERIMENTS ON CHORDAL GRAPH HELLIFICATION." Kent State University / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=kent1494430064980414.
Full textIbarra, Louis Walter. "Dynamic algorithms for chordal and interval graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/NQ58573.pdf.
Full textBhaduri, Sudipta. "Finding A Maximum Clique of A Chordal Graph by Removing Vertices of Minimum Degree." Kent State University / OhioLINK, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=kent1208869783.
Full textSacramento, Jonathan. "Computing the leafage of chordal graphs /." Leeds : University of Leeds, School of Computer Studies, 2008. http://www.comp.leeds.ac.uk/fyproj/reports/0708/Sacramento.pdf.
Full textPogorelcnik, Romain. "Decomposition by complete minimum separators and applications." Thesis, Clermont-Ferrand 2, 2012. http://www.theses.fr/2012CLF22301/document.
Full textWe worked on clique minimal separator decomposition. In order to compute this decomposition on a graph G we need to compute the minimal separators of its triangulation H. In this context, the first efforts were on finding a clique minimal separators in a chordal graph. We defined a structure called atom tree inspired from the clique tree to compute and represent the final products of the decomposition, called atoms. The purpose of this thesis was to apply this technique on biological data. While we were manipulating this data using Galois lattices, we noticed that the clique minimal separator decomposition allows a divide and conquer approach on Galois lattices. One biological application of this thesis was the detection of fused genes which are important evolutionary events. Using algorithms we produced in the course of along our work we implemented a program called MosaicFinder that allows an efficient detection of this fusion event and their pooling. Another biological application was the extraction of genes of interest using expression level data. The atom tree structure allowed us to have a good visualization of the data and to be able to compute large datasets
Odom, Richard M. "Edge completion sequences for classes of chordal graphs." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Service, 1995. http://handle.dtic.mil/100.2/ADA302986.
Full textCarroll, Thomas. "Edge annihilation sequences for classes of chordal graphs." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1996. http://handle.dtic.mil/100.2/ADA313817.
Full textAltomare, Christian J. "Degree Sequences, Forcibly Chordal Graphs, and Combinatorial Proof Systems." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1259546079.
Full textLi, Xuechao. "Chords of longest circuits of graphs." Morgantown, W. Va. : [West Virginia University Libraries], 2001. http://etd.wvu.edu/templates/showETD.cfm?recnum=2141.
Full textTitle from document title page. Document formatted into pages; contains vi, 57 p. : ill. Includes abstract. Includes bibliographical references (p. 56-57).
Krishnamurthy, Chandra Mohan. "The Maximum Induced Matching Problem for Some Subclasses of Weakly Chordal Graphs." University of Dayton / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006.
Full textKammer, Frank [Verfasser], and Torben [Akademischer Betreuer] Hagerup. "Treelike and Chordal Graphs: Algorithms and Generalizations / Frank Kammer. Betreuer: Torben Hagerup." Augsburg : Universität Augsburg, 2012. http://d-nb.info/1077700814/34.
Full textGrußien, Berit. "Capturing Polynomial Time and Logarithmic Space using Modular Decompositions and Limited Recursion." Doctoral thesis, Humboldt-Universität zu Berlin, 2017. http://dx.doi.org/10.18452/18548.
Full textThis theses is making contributions to the field of descriptive complexity theory. First, we look at the main open problem in this area: the question of whether there exists a logic that captures polynomial time (PTIME). We consider classes of graphs that are closed under taking induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed-point logic with counting (FP+C) captures PTIME on the class of permutation graphs and the class of chordal comparability graphs. We also prove that the modular decomposition tree is definable in symmetric transitive closure logic with counting (STC+C), and therefore, computable in logarithmic space. Further, we introduce a new logic for the complexity class logarithmic space (LOGSPACE). We extend first-order logic with counting by a new operator that allows it to formalize a limited form of recursion which can be evaluated in logarithmic space. We prove that the resulting logic LREC is strictly more expressive than deterministic transitive closure logic with counting (DTC+C) and that it is strictly contained in FP+C. We show that LREC captures LOGSPACE on the class of directed trees. We also study an extension LREC= of LREC that has nicer closure properties and that, unlike LREC, is more expressive than symmetric transitive closure logic (STC). We prove that LREC= captures LOGSPACE on the class of interval graphs and on the class of chordal claw-free graphs.
Mason, Richard. "A chordal sparsity approach to scalable linear and nonlinear systems analysis." Thesis, University of Oxford, 2015. https://ora.ox.ac.uk/objects/uuid:c4a978aa-185e-4029-a887-6aa2ab9efb37.
Full textAcan, Huseyin. "An Enumerative-Probabilistic Study of Chord Diagrams." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487.
Full textAsh, Patricia. "Dominating cycles, Hamilton cycles and cycles with many chords in 2-connected graphs." Thesis, Goldsmiths College (University of London), 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.490379.
Full textArredondo, Ryan. "Properties of Graphs Used to Model DNA Recombination." Scholar Commons, 2014. https://scholarcommons.usf.edu/etd/4979.
Full textXu, Binbin. "L'identité de Pleijel hyperbolique, la métrique de pression et l'extension centrale du groupe modulaire via quantification de Chekhov-Fock." Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM068/document.
Full textThis thesis consists of three parts corresponding to the three subjects that I have studied during the last three years.The first part contains the study of the chord length distribution associated to a compact (or non-compact) domain in the hyperbolic plane. We prove the hyperbolic Pleijel identity. By using this identity, we find new approaches to the Crofton's formula and the isoperimetric inequality, and then compute the chord length distribution associated to an ideal triangle and that associated to an ideal quadrilateral. Then we prove the analogue results for the simply connected Riemannian surface with constant curvature.The second part of this thesis (Chapter 5) consists of the study of the pressuremetric on the Teichmüller space of one-holed torus. By studying the degeneration of the torus when the boundary length goes to infinity, we find the relation of this metric to the pressure metric on the moduli space of metric graphs. Then we study the entropy function and prove that it is not constant on the symplectic leaf of the Teichmüller space of a bordered surface.Finally, the third part concerns the quantization of the Teichmüller space of a punctured surface. In this chapter, we study the central extension of the mapping class group coming from the quantization and compute its cohomology class which is 12 times the Meyer class plus the Euler classes associated to punctures
Golz, Marcel. "Parametric quantum electrodynamics." Doctoral thesis, Humboldt-Universität zu Berlin, 2019. http://dx.doi.org/10.18452/19776.
Full textThis thesis is concerned with the study of Schwinger parametric Feynman integrals in quantum electrodynamics. Using a variety of tools from combinatorics and graph theory, significant simplification of the integrand is achieved. After a largely self-contained introduction to Feynman graphs and integrals, the derivation of the Schwinger parametric representation from the standard momentum space integrals is reviewed in full detail for both scalar theories and quantum electrodynamics. The derivatives needed to express Feynman integrals in quantum electrodynamics in their parametric version are found to contain new types of graph polynomials based on cycle and bond subgraphs. Then the tensor structure of quantum electrodynamics, products of Dirac matrices and their traces, is reduced to integer factors with a diagrammatic interpretation of their contraction. Specifically, chord diagrams with a particular colouring are used. This results in a parametric integrand that contains sums of products of cycle and bond polynomials over certain subsets of such chord diagrams. Further study of the polynomials occurring in the integrand reveals connections to other well-known graph polynomials, the Dodgson and spanning forest polynomials. This is used to prove an identity that expresses some of the very large sums over chord diagrams in a very concise form. In particular, this leads to cancellations that massively simplify the integrand.
HE, JIN-WEN, and 何錦文. "Fast parallel algorithms related to chordal graph." Thesis, 1988. http://ndltd.ncl.edu.tw/handle/66639018202847950320.
Full text國立清華大學
計算機管理決策研究所
76
Chordal graph 與相當多的問題有很大的關連,尤其是有關解疏散式線性方程組的問 題。在本篇博士論文裹,我們提出若干快速平行計算方法來解一些與 Chordal graph 有關的問題。這些問題可分成兩個部分。第一個部分是直接與Chordal graph 有關的 問題。這部分的問題包括認定Chordal graph 的問題及在Chordal graph 上找一些特 定的事物,這些事物包括maximal clique,clique true ,minimum coloring,及pe rfect elimination scheme。我們的做法比起以前人的做法有很大的改進。我們把解 這些問題所需的處理器個數從0( n)或0( n)降到0( n),並且把所需 的計算時間從0(logn)降到0(logn),其中n 是代表頂點的個數。我們第二部 分解的問題是解疏散式三角線性方程組。我們提出兩個平行計算方法來解這個問題。 這兩個方法都比前人的解法快很多。第一個方法是解一般的疏散式三角線性方程組。 一些模擬的結果顯示這個方法的執行時間隨給定方程組的疏散性而改變。第二個方法 ,利用第一個方法當副程式,是用來解一些特定的疏散線性方程組,這些方程組的係 數矩陣是得自某一對稱矩陣的LU分解。我們應用很多Chordal graph 的特性來設計第 二個計算方法並分析這兩個計算方法的執行效率。
"Linear time algorithms for graphs close to chordal graphs." 2003. http://library.cuhk.edu.hk/record=b5891620.
Full textThesis (M.Phil.)--Chinese University of Hong Kong, 2003.
Includes bibliographical references (leaves 51-54).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Statement of problems --- p.1
Chapter 1.2 --- Notation and definitions --- p.3
Chapter 1.3 --- Graph families --- p.4
Chapter 1.4 --- Related work --- p.5
Chapter 1.4.1 --- Graph modification problems --- p.5
Chapter 1.4.2 --- Independent set --- p.6
Chapter 1.5 --- Overview of the thesis --- p.7
Chapter 2 --- Recognition of Nearly Chordal Graphs --- p.8
Chapter 2.1 --- Critical edges not in triangles --- p.9
Chapter 2.2 --- Critical edges in triangles --- p.10
Chapter 2.3 --- A linear time algorithm --- p.13
Chapter 3 --- Recognition of Almost Chordal Graphs --- p.15
Chapter 3.1 --- Minimal separator --- p.16
Chapter 3.2 --- "All chordless cycles passing through the minimal (x, z)-separator S" --- p.18
Chapter 3.3 --- Algorithm for almost chordal graphs recognition --- p.22
Chapter 3.4 --- Another approach to find a critical vertex if all chordless cycles pass through S --- p.26
Chapter 3.5 --- A linear algorithm for all chordless cycles passing through S --- p.28
Chapter 4 --- Maximum Independent Bases of Chordal Graphs --- p.32
Chapter 4.1 --- Maximum independent base --- p.32
Chapter 4.1.1 --- Finding a maximum independent set of a chordal graph . --- p.33
Chapter 4.1.2 --- Another approach to prove the algorithm --- p.33
Chapter 4.1.3 --- Maximum independent base --- p.34
Chapter 4.1.4 --- Vertices in the maximum independent base --- p.36
Chapter 4.1.5 --- A linear time algorithm --- p.38
Chapter 4.2 --- Generating all maximum independent sets --- p.39
Chapter 4.2.1 --- Relation between two maximum independent sets --- p.39
Chapter 4.2.2 --- Algorithm --- p.40
Chapter 4.3 --- Maximum induced split graph of a chordal graph --- p.43
Chapter 4.3.1 --- Property of maximum induced split subgraph --- p.44
Chapter 4.3.2 --- A linear time algorithm --- p.45
Chapter 5 --- Concluding Remarks --- p.48
Chapter 5.1 --- Summary of results --- p.48
Chapter 5.2 --- Open problems --- p.48
Bibliography --- p.51
Klem, Estiaan Murrell. "Non-chordal patterns associated with the positive definite completion problem / Estiaan Murrell Klem." Thesis, 2015. http://hdl.handle.net/10394/15334.
Full textMSc (Mathematics), North-West University, Potchefstroom Campus, 2015
Yang, Feiran. "New results on broadcast domination and multipacking." Thesis, 2015. http://hdl.handle.net/1828/6627.
Full textGraduate
Jampani, Krishnam Raju. "Simultaneous Graph Representation Problems." Thesis, 2011. http://hdl.handle.net/10012/5793.
Full textChiang, Wei-Ling, and 江韋伶. "A Linear Time Algorithm for the Simple Moplex Ordering of a Strongly Chordal Graph." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/26826356427901784124.
Full text國立臺北商業技術學院
資訊與決策科學研究所
102
Berry [A. Berry, J. P. Bordat, Moplex elimination orderings, Electronic Notes in Discrete Mathematics, 8 (2001) 6--9] proved that a graph G is choral if and only if G admits a moplex ordering. In this thesis, we also prove that a strongly chordal graph has a similar ordering namely simple moplex ordering. Then, we propose an algorithm that can be run in linear time to find such an ordering.
Connon, Emma. "Generalizing Fröberg's Theorem on Ideals with Linear Resolutions." 2013. http://hdl.handle.net/10222/38565.
Full textChen, Jan-Hau, and 陳建豪. "Relations of Chordal Probe Graphs and Tolerance Graphs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/87804271940117392669.
Full text國立臺灣海洋大學
資訊工程學系
93
Tolerance graphs arise from the intersection of intervals with varying tolerances in a way that generalizes both interval graphs and permutation graphs. In this paper we discuss the subclasses of tolerance graphs, interval probe graphs, and chordal probe graphs. We show that G is chordal graph without T3 or , then G is an interval probe graph if and only if G is a tolerance graph. We also introduce the class of chordal probe graphs which are a generalization of both interval probe graphs and chord graphs.
Lai, Yu-Ren, and 賴育仁. "Some Problems on Chordal Probe Graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/25771468419118238317.
Full textWu, Wu-Hsiung, and 吳武雄. "L(2,1)-labeling on Chordal Graphs." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/06413108054791405000.
Full text國立中正大學
資訊工程研究所
91
For a general graph $G=(V,E)$, an {\bf $L$(2, 1)-$labeling$} of $G$ is a function $f$ from the vertex set $V$ to the set of nonnegative integers such that $|f(x)-f(y)|\geq 2$ if $d(x,y)=1$ and $|f(x)-f(y)|\geq 1$ if $d(x, y)=2$, where $d(x, y)$ is the minimum length of a path between $x$ and $y$ in $G$, called the distance between $x$ and $y$. A $k$-$L$(2, 1)-$labeling$ is an $L$(2, 1)-$labeling$ such that no label is greater than $k$. The $L$(2, 1)-$labeling$ $number$ of $G$, denoted by $\lambda(G)$, is the smallest number $k$ such that $G$ has a $k$-$L$(2,1)-$labeling$. The $L$(2, 1)-$labeling$ problem has been extensively studied during the past ten years. These include bounds for general graphs as well as special graphs such as trees, chordal graphs, strongly chordal graphs; exact values for paths, cycles, etc. In this paper, we focus on the $L$(2, 1)-$labeling$ problem on chordal graphs. Sakai \cite{SAK94} showed that $\lambda(G) \leq \frac{(\Delta + 3)^2}{4}$ for any chordal graph $G$ with maximum degree $\Delta$. We improve this bound to $\frac{\Delta^2}{4} + 6$.
Chang, Yu-Wei, and 張育瑋. "The 2-center problem in chordal graphs." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/78683245220635657035.
Full text國立臺北商業技術學院
資訊與決策科學研究所
100
In a graph G, the p-center problem is to identify p vertices of G for locating some kind of facilities such that the maximum among the distances from all vertices to their nearest facility is minimized. In this thesis, we propose an O(n)-time algorithm for computing a 2-center in a chordal graph with maximum degree at most three, where a graph is chordal if every induced cycle of length at least four has a chord, and n is the number of vertices in the graph.
戴昆成. "Some Problems on Weakly Chordal Graphs, co-Perfect Orderable Graphs and Alternately Orientable Graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/52490934450689952121.
Full textHsu, Chung Chang, and 徐忠長. "On Two Location Problems in Strongly Chordal Graphs." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/00511923535022306480.
Full text國立中正大學
資訊工程研究所
81
Given a simple graph G, which is composed of the set of vertices V and the set of edges E, a set of vertices D is a dominating set if every vertex in V is adjacent to at least one vvertex in D. In this thesis, we define two terms related to the dominating set. One is k-fault tolerant dominating set which is a set D of V such that the cardinality of the intersection of D and the close neighborhood of v is greater than k for every v in V. The other is minimum h-disjoint dominating set problem which is to find a minimum h-disjoint dominating set such that each vertex in V is adjacent to at least h vertices in this set. Then, we partititon the set into h disjoint sets, and each set is a dominating set. In this thesis, a linear time algorithm is proposed to solve the k- fault tolerant dominating set problem and the minimum h- disjoint dominating set problem on strongly chordal graphs when the strong elimination ordering is given and another linear time algorithm is used to partition this set into h disjoint sets. As a byproduct, we will show strongly chordal graphs to be domatically perfect which is new-defined. Further, we relax the disjointness of these dominating sets. An linear time algorithm is found to derive the minimum cardinality of the two minimum dominating sets on, the subclasses of strongly chordal graphs, interval graphs.
Chu, Kuan-Ting, and 褚冠廷. "Mutual Transferability of Dominating Sets in Strongly Chordal Graphs and Cactus Graphs." Thesis, 2018. http://ndltd.ncl.edu.tw/handle/4td2ug.
Full textChen, Ya-Mei, and 陳雅玫. "The Fault Tolerant Domination Problem on Strongly Chordal Graphs." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/89509799514631971665.
Full text國立中正大學
資訊工程研究所
89
Given a graph G = (V, E) and a fault tolerant function f from V to N, a dominating set D(subset of V) is fault tolerant if | D∩N[v] | >= f(v) for all v in V. Given a graph G = (V, E) and a function g,from V to integers, the weight of g is defined as w(g) =Σ(v in V) g(v). For a vertex v in V, let g[v] =Σ(u in N[v]) g(u). A signed dominating function of G is a function g,from V to {-1,1}, such that g[v] >= 1 for all v in V. The signed domination number rs(G)(gamma_s(G)) of G is the minimum weight of a signed dominating function on G. We call a signed dominating function of a weight rs(G) as a rs-function of G. The signed domination problem is to find a rs-function of a graph. In this paper, we propose a new concept, fault tolerant domination. It is a generalization of some kinds of domination problems. Furthermore, we give an O(n + m) time algorithm to find a fault tolerant dominating set of minimum cardinality of a given strongly chordal graph G and a fault tolerant function f of G.
Tsay, Ming Shiann, and 蔡明憲. "Efficient Algorithms for Some Problems on Subclasses of Chordal Graphs." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/25117474535146377267.
Full text國立中正大學
資訊工程研究所
82
Two problems are discussed in this thesis. One is the all pairs shortest paths problem, and the other is the minimum weight k dominating sets problem. The all pairs shortest paths problem is applied extensively. In the past, scholars paid attention to reducing the time complexity of solving such problem on general graphs. They achieved .OMICRON.(n^3) time complexity in worst case, and .OMICRON.(n^2log n) time complexity in average case. When we restrict the problem to being solved on some special graphs, the optimal algorithm with time complexity .OMICRON.( n^2) can be found. In this thesis, the problem is discussed on chordal graphs and on strongly chordal graphs. We apply the result to reduce the time complexities of solving the k- domination problem, the k-stability problem, the k-domatic partition problem, and the k-coloring problem. The minimum weight k dominating sets problem is an extension of the domination problem. The domination problem is NP-complete on general graphs, so is the minimum weight k dominating sets problem. Fortunately, on interval graphs, we can transform the minimum weight k dominating sets problem into the minimum cost network flow problem with flow .absolute.(f)=k. The idea is from the algorithm for solving the maximum k-covering problem on transitive graphs proposed by Sarrafzadeh and Lou. The minimum cost network flow problem can be solved in .OMICRON.( km) time by the algorithm designed by Edmonds and Karp, if all the costs are nonnegative. We apply the algorithm to solve the minimum weight k dominating sets problem in .OMICRON.(kn^2) time even the costs are negative.
Tsai, Yun-Cheng, and 蔡芸琤. "Some Results On Bounded Tolerance, Cocomparability, And Weakly Chordal Graphs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/60041434999721557614.
Full text國立臺灣海洋大學
資訊工程學系
93
Tolerance graphs were first introduced by Golumbic [1] in 1984, which generalize both interval and permutation graphs with a lot of applications. The main theorem is: A tolerance graph is bounded, and then it is a cocomparability graph. However the converse of the theorem is still unsolved so far. We give a complete of proof of that by using Knotting graph [3] that is: A tolerance graph is a cocomparability graph then it is bounded. With some related topic, we also prove that a weakly chordal graph which is AT-free and a comparability graph, then it is a permutation graph. Finally we construct a hierarchy of classes of the related graphs and give some separating examples.
Chen, Yi Hua, and 陳怡華. "Algorithmic Aspects of the Generalized Clique-Transversal Set on Chordal Graphs." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/27300462804839335443.
Full text國立中正大學
資訊工程研究所
81
Given a graph G = (V, E), a set T is called a clique- transversal set if absolute (T intersection C) .gsidm. 1 for every clique C in G, and define the clique-transversal number as the minimum cardinality of a clique-transversal set. The clique-transversal problem is to determine the clique- transversal number. More, if each clique is associated with an integer, then we can generalize the clique-transversal set to the generalized clique-transversal set, that is, T is a generalized clique-transversal set if absolute(T intersection Ci) .gsidm. ri for every clique Ci in G. Hence the generalized clique-transversal problem is, given a graph G =(V ,E) and a relation R = .lbrace.(Ci, ri).rbrace., to determine the minimum cardinality of a generalized clique-transversal set, called the generalized clique-transversal number with respect to R. We first give an efficient algorithm for the generalized clique- transversal problem on strongly chordal graphs. And then show the NP-completeness of the clique-transversal problem on the undirected path graphs and k-trees. Hence the generalized clique -transversal problem is NP-complete on undirected path graphs and k-trees, since the clique-transversl problem is a special case of the generalized clique-transversal problem. More, the generalized clique-transversal problem has some clique-related problems -- the maximum q-colorable subgraph, the generalized vertex covering and the neighborhood-covering problems. This problems can be done easily as the generalized clique-transversal problem has solved. We also consider the algorithmic complexity of these problems an all graphs mentioned above.
Chiu, Guei-Lin, and 邱圭琳. "A Certifying Algorithm for Finding Hinge Vertices of Strongly Chordal Graphs." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/36469603676772326548.
Full text國立暨南國際大學
資訊工程學系
96
Let G = (V, E) be a graph, and let G−u be the subgraph of G induced by the vertex set V(G) − {u}. A vertex u ∈ V(G) is said to be a hinge vertex of G if and only if there exist two vertices x, y ∈ V(G − u) such that dG−u(x, y) > dG(x, y), where dG(x , y) is the distance (i.e., the length of a shortest path) between x and y in G. A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence proving that the answer has not been compromised by a bug in the implementation. In this paper, we present an Ο(n + m) time certifying algorithm for finding all hinge vertices of strongly chordal graphs.
Ding, Kun-Fu, and 丁坤福. "Some Results of Incidence Coloring on Generalized Petersen Graphs and Chordal Rings." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/44656311289030408998.
Full text明志科技大學
工業工程與管理系碩士班
103
An incidence of G is a pair (v, e) where v ∈ V(G) is a vertex and e ∈ E(G) is an edge incident with v. Two incidences (v, e) and (w, f) are adjacent if one of the following holds: (a) v = w, (b) e = f or (c) vw = e or vw = f. Let I(G) be the set consisting of all incidences of a graph G. A proper incidence coloring of G is a mapping from I(G) to a set of colors such that adjacent incidences are assigned distinct colors. The smallest number of colors required for such a coloring is called the incidence coloring number of G, and is denoted by χi(G). In this paper, we study the incidence coloring on generalized Petersen graphs GP(n, k) and Chordal Rings CR(N, d). We first assure that 4 ≤ χi(GP(n, k)) ≤ 5. Furthermore, we provide the following results: (i) χi(GP(n, k)) = 5 if n is odd, (ii) χi(GP(n, 2)) = 5, and (iii) χi(GP(n, k)) = 4 if n ≡ 0 (mod 4) and k is odd. Then, we have the following results on χi(CR(N, d)): (i) χi(CR(N, d)) = 5, if N ≡ 0 (mod 5) and d = 2 or 3, (ii) χi(CR(N, 2)) = 6, if N mod 5 ≠ 0, and (iii) χi(CR(N, 3)) = 6, if N ≡ 2 (mod 5).
Mathew, Rogers. "Boxicity And Cubicity : A Study On Special Classes Of Graphs." Thesis, 2012. http://etd.iisc.ernet.in/handle/2005/2320.
Full textLin, Cheng-Ying, and 林政瑩. "An O(n3)-Time Algorithm for Minimum Fill-in Problem on Chordal Bipartite Graphs." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/20166405857904142646.
Full text國立中正大學
資訊工程所
95
A graph is a chordal bipartite graph if it is bipartite and every cycle greater than four has a chord. For an arbitrary graph, a minimum fill-in of G refers to a minimum cardinality set E’ from Ē = {(u, v) E : u, v ∈ V } such that G = (V,E ∪E’) is chordal. Given a graph G = (V, E) and a subset X of V , G[X] is called an induced cycle of length l, denoted by Cl, if G[X] is a cycle and its length is l. For a graph G = (V,E), and a set E’ from Ē = {(u, v) E : u ∈ V and v ∈ V } is said to be a C4-destroying set if for every induced cycle (w, x, y, z,w) of length four in G, the edge (w, y) or (x, z) is in E’. Chang proved that for a chordal bipartite G = (S, T,E) and E’ be a minimum C4-destroying set of G, G’ = (S ∪ T,E ∪ E’) is a chordal graph. In this paper, we show that the minimum C4-destroying set of a chordal bipartite graph can be found in O(n3) time. Therefore the minimum fill-in problem on chordal bipartite graphs can be solved in O(n3) time.
"Erdos--Ko--Rado Theorems: New Generalizations, Stability Analysis and Chvatal's Conjecture." Doctoral diss., 2011. http://hdl.handle.net/2286/R.I.8895.
Full textDissertation/Thesis
Ph.D. Mathematics 2011