Dissertations / Theses on the topic 'Spanning graphs of hypercubes'
To see the other types of publications on this topic, follow the link: Spanning graphs of hypercubes.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Spanning graphs of hypercubes.'
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.
1
Kobeissi, Mohamed. "Plongement de graphes dans l'hypercube." Phd thesis, Grenoble 1, 2001. https://theses.hal.science/tel-00004683.
Full textAbstract:
Le but principal de ce manuscrit est de montrer que certaines familles de graphes sont des graphes plongeables dans l'hypercube. Un problème d'une autre nature sera traité, il concerne la partition de l'hypercube en des cycles sommet-disjoints de longueur paires. Nous prouvons que l'hypercube de dimension n peut être partitionné en k cycles sommet-disjoints si k
2
Vasquez, Maria Rosario. "An investigation of super line graphs of hypercubes." Virtual Press, 1993. http://liblink.bsu.edu/uhtbin/catkey/865951.
Full textAbstract:
Graphs, as mathematical objects, play a dominant role in the study of network modeling, VLSI design, data structures, parallel computation, process scheduling and in a variety of other areas of computer science. Hypercubes are one of the preferred architectures for parallel computation, and a study of some properties of the hypercubes motivated this thesis.The concept of super line graphs, introduced by Bagga at el, generalizes the notion of line graphs. In this thesis several graph theoretic properties of super line graphs of hypercubes are studied. In particular the super line graphs of index two of hypercubes are investigated and some exact results and precise characterizations are found.Department of Computer Science
3
Montgomery, Richard Harford. "Minors and spanning trees in graphs." Thesis, University of Cambridge, 2015. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.709278.
Full text
4
Knox, Fiachra. "Embedding spanning structures in graphs and hypergraphs." Thesis, University of Birmingham, 2013. http://etheses.bham.ac.uk//id/eprint/4027/.
Full textAbstract:
In this thesis we prove three main results on embeddings of spanning subgraphs into graphs and hypergraphs. The first is that for log⁵⁰ n/n \ ≤ p ≤ 1-n⁻¹/⁴ log⁹ n, a binomial random graph G ~ G_n,p contains with high probability a collection of └δ(G)/2┘ edge disjoint Hamilton cycles (plus an additional edge-disjoint matching if δ(G) is odd), which confirms for this range of p a conjecture of Frieze and Krivelevich. Secondly, we show that any 'robustly expanding' graph with linear minimum degree on sufficiently many vertices contains every bipartite graph on the same number of vertices with bounded maximum degree and sublinear bandwidth. As corollaries we obtain the same result for any graph which satisfies the Ore-type condition d(x) + d(y) ≥ (1 + η)n for non-adjacent vertices x and y, or which satisfies a certain degree sequence condition. Thirdly, for γ > 0 we give a polynomial-time algorithm for determining whether or not a k-graph with minimum codegree at least (1/k + γ)n contains a perfect matching. This essentially answers a question of Rodl, Rucinski and Szemeredi. Our algorithm relies on a strengthening of a structural result of Keevash and Mycroft. Finally and additionally, we include a short note on Maker-Breaker games.
5
Mahoney, James Raymond. "Tree Graphs and Orthogonal Spanning Tree Decompositions." PDXScholar, 2016. http://pdxscholar.library.pdx.edu/open_access_etds/2944.
Full textAbstract:
Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as clique decomposition, planarity, and automorphism groups. We also investigate and present a number of new results on orthogonal tree decompositions of complete graphs.
6
Cairncross, Emily. "Proper 3-colorings of cycles and hypercubes." Oberlin College Honors Theses / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1621606265779497.
Full text
7
Wong, Wiseley. "Spanning trees, toughness, and eigenvalues of regular graphs." Thesis, University of Delaware, 2013. http://pqdtopen.proquest.com/#viewpdf?dispub=3595000.
Full textAbstract:
Spectral graph theory is a branch of graph theory which finds relationships between structural properties of graphs and eigenvalues of matrices corresponding to graphs. In this thesis, I obtain sufficient eigenvalue conditions for the existence of edge-disjoint spanning trees in regular graphs, and I show this is best possible. The vertex toughness of a graph is defined as the minimum value of [special characters omitted], where S runs through all subsets of vertices that disconnect the graph, and c(G\S ) denotes the number of components after deleting S. I obtain sufficient eigenvalue conditions for a regular graph to have toughness at least 1, and I show this is best possible. Furthermore, I determine the toughness value for many families of graphs, and I classify the subsets S of each family for when this value is obtained.
8
King, Andrew James Howell. "On decomposition of complete infinite graphs into spanning trees." Thesis, University of Reading, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.253454.
Full text
9
Zhang, Yuanping. "Counting the number of spanning trees in some special graphs /." View Abstract or Full-Text, 2002. http://library.ust.hk/cgi/db/thesis.pl?COMP%202002%20ZHANG.
Full text
10
Koo, Cheng Wai. "A Bound on the Number of Spanning Trees in Bipartite Graphs." Scholarship @ Claremont, 2016. https://scholarship.claremont.edu/hmc_theses/73.
Full textAbstract:
Richard Ehrenborg conjectured that in a bipartite graph G with parts X and Y, the number of spanning trees is at most the product of the vertex degrees divided by |X|⋅|Y|. We make two main contributions. First, using techniques from spectral graph theory, we show that the conjecture holds for sufficiently dense graphs containing a cut vertex of degree 2. Second, using electrical network analysis, we show that the conjecture holds under the operation of removing an edge whose endpoints have sufficiently large degrees.
Our other results are combinatorial proofs that the conjecture holds for graphs having |X| ≤ 2, for even cycles, and under the operation of connecting two graphs by a new edge.
We also make two new conjectures based on empirical data, each of which is stronger than Ehrenborg's conjecture.
11
Ebsen, Oliver-Andre [Verfasser]. "Homomorphism thresholds and embeddings of spanning subgraphs in dense graphs / Oliver-Andre Ebsen." Hamburg : Staats- und Universitätsbibliothek Hamburg Carl von Ossietzky, 2020. http://d-nb.info/1241249172/34.
Full text
12
McLeod, Tyson. "Designing an algorithm to build communities by combining semi-cliques spanning multiple graphs." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-450174.
Full textAbstract:
Community detection is an important graph mining task and one of the most researched problems in its field of study. One reason for this is its applicability in a variety of disciplines ranging from biology to computer science. Community detection methods differ, however, and a major reason for this is due to the fact that there does not exist a unique definition for what a community is. This project involved creating a new method for detecting and building communities for a specific type of network represented by multi-layered graphs, where each layer represents an edge type/ type of relation. More specifically, an algorithm for detecting and building communities in multi-layered graphs was built by first implementing a method to detect semi-cliques spanning multiple graphs, and then integrating the method with a second method which builds communities using multi-layered cliques. The new method wasthen tested on synthetic as well as real-world data to demonstrate functionality and test validity.
13
Solomyak, Margarita. "Essential spanning forests and electric networks in groups /." Thesis, Connect to this title online; UW restricted, 1997. http://hdl.handle.net/1773/5767.
Full text
14
Parczyk, Olaf [Verfasser], Yury [Gutachter] Person, and David [Gutachter] Conlon. "Spanning structures in random graphs and hypergraphs / Olaf Parczyk ; Gutachter: Yury Person, David Conlon." Frankfurt am Main : Universitätsbibliothek Johann Christian Senckenberg, 2018. http://d-nb.info/115485292X/34.
Full text
15
Silvestri, Selene. "Models and Algorithms for Some Covering Problems on Graphs." Thesis, Universita degli studi di Salerno, 2016. http://hdl.handle.net/10556/2303.
Full textAbstract:
2014 - 2015Several real-life problems as well as problems of theoretical importance within the field of Operations Research are combinatorial in nature. Combinatorial Optimization deals with decision-making problems defined on a discrete space. Out of a finite or countably infinite set of feasible solutions, one has to choose the best one according to an objective function. Many of these problems can be modeled on undirected or directed graphs. Some of the most important problems studied in this area include the Minimum Spanning Tree Problem, the Traveling Salesman Problem, the Vehicle Routing Problem, the Matching Problem, the Maximum Flow Problem. Some combinatorial optimization problems have been modeled on colored (labeled) graphs. The colors can be associated to the vertices as well as to the edges of the graph, depending on the problem. The Minimum Labeling Spanning Tree Problem and the Minimum Labeling Hamiltonian Cycle Problem are two examples of problems defined on edge-colored graphs. Combinatorial optimization problems can be divided into two groups, according to their complexity. The problems that are easy to solve, i.e. problems polynomially solvable, and those that are hard, i.e. for which no polynomial time algorithm exists. Many of the well-known combinatorial optimization problems defined on graphs are hard problems in general. However, if we know more about the structure of the graph, the problems can become more tractable. In some cases, they can even be shown to be polynomial-time solvable. This particularly holds for trees...[edited by Author]
XIV n.s.
16
Law, Hiu-Fai. "Trees and graphs : congestion, polynomials and reconstruction." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:54190b51-cd9d-489e-a79e-82ecdf15b4c5.
Full textAbstract:
Spanning tree congestion was defined by Ostrovskii (2004) as a measure of how well a network can perform if only minimal connection can be maintained. We compute the parameter for several families of graphs. In particular, by partitioning a hypercube into pieces with almost optimal edge-boundaries, we give tight estimates of the parameter thereby disproving a conjecture of Hruska (2008). For a typical random graph, the parameter exhibits a zigzag behaviour reflecting the feature that it is not monotone in the number of edges. This motivates the study of the most congested graphs where we show that any graph is close to a graph with small congestion. Next, we enumerate independent sets. Using the independent set polynomial, we compute the extrema of averages in trees and graphs. Furthermore, we consider inverse problems among trees and resolve a conjecture of Wagner (2009). A result in a more general setting is also proved which answers a question of Alon, Haber and Krivelevich (2011). After briefly considering polynomial invariants of general graphs, we specialize into trees. Three levels of tree distinguishing power are exhibited. We show that polynomials which do not distinguish rooted trees define typically exponentially large equivalence classes. On the other hand, we prove that the rooted Ising polynomial distinguishes rooted trees and that the Negami polynomial determines the subtree polynomial, strengthening results of Bollobás and Riordan (2000) and Martin, Morin and Wagner (2008). The top level consists of the chromatic symmetric function and it is proved to be a complete invariant for caterpillars.
17
Zelke, Mariano. "Algorithms for streaming graphs." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2009. http://dx.doi.org/10.18452/15912.
Full textAbstract:
Für einen Algorithmus zum Lösen eines Graphenproblems wird üblicherweise angenommen, dieser sei mit wahlfreiem Zugriff (random access) auf den Eingabegraphen G ausgestattet, als auch mit einem Arbeitsspeicher, der G vollständig aufzunehmen vermag. Diese Annahmen erweisen sich als fragwürdig, wenn Graphen betrachtet werden, deren Größe jene konventioneller Arbeitsspeicher übersteigt. Solche Graphen können nur auf externen Speichern wie Festplatten oder Magnetbändern vorrätig gehalten werden, auf denen wahlfreier Zugriff sehr zeitaufwändig ist. Um riesige Graphen zu bearbeiten, die auf externen Speichern liegen, hat Muthukrishnan 2003 das Modell eines Semi-Streaming Algorithmus vorgeschlagen. Dieses Modell beschränkt die Größe des Arbeitsspeichers und verbietet den wahlfreien Zugriff auf den Eingabegraphen G. Im Gegenteil wird angenommen, die Eingabe sei ein Datenstrom bestehend aus Kanten von G in beliebiger Reihenfolge. In der vorliegenden Dissertation entwickeln wir Algorithmen im Semi-Streaming Modell für verschiedene Graphenprobleme. Für das Testen des Zusammenhangs und der Bipartität eines Graphen, als auch für die Berechnung eines minimal spannenden Baumes stellen wir Algorithmen vor, die asymptotisch optimale Laufzeiten erreichen. Es ist bekannt, dass kein Semi-Streaming Algorithmus existieren kann, der ein größtes gewichtetes Matching in einem Graphen findet. Für dieses Problem geben wir den besten bekannten Approximationsalgorithmus an. Schließlich zeigen wir, dass sowohl ein minimaler als auch ein maximaler Schnitt in einem Graphen nicht von einem Semi-Streaming Algorithmus berechnet werden kann. Für beide Probleme stellen wir randomisierte Approximationsalgorithmen im Semi-Streaming Modell vor.An algorithm solving a graph problem is usually expected to have fast random access to the input graph G and a working memory that is able to store G completely. These powerful assumptions are put in question by massive graphs that exceed common working memories and that can only be stored on disks or even tapes. Here, random access is very time-consuming. To tackle massive graphs stored on external memories, Muthukrishnan proposed the semi-streaming model in 2003. It permits a working memory of restricted size and forbids random access to the input graph. In contrast, the input is assumed to be a stream of edges in arbitrary order. In this thesis we develop algorithms in the semi-streaming model approaching different graph problems. For the problems of testing graph connectivity and bipartiteness and for the computation of a minimum spanning tree, we show how to obtain running times that are asymptotically optimal. For the problem of finding a maximum weighted matching, which is known to be intractable in the semi-streaming model, we present the best known approximation algorithm. Finally, we show the minimum and the maximum cut problem in a graph both to be intractable in the semi-streaming model and give semi-streaming algorithms that approximate respective solutions in a randomized fashion.
18
Reich, Alexander [Verfasser], and Ekkehard [Akademischer Betreuer] Köhler. "Cycle bases of graphs and spanning trees with many leaves - complexity results on planar and regular graphs / Alexander Reich. Betreuer: Ekkehard Köhler." Cottbus : Universitätsbibliothek der BTU Cottbus, 2014. http://d-nb.info/1051310636/34.
Full text
19
Turner, Bethany. "Embeddings of Product Graphs Where One Factor is a Hypercube." VCU Scholars Compass, 2011. http://scholarscompass.vcu.edu/etd/2455.
Full textAbstract:
Voltage graph theory can be used to describe embeddings of product graphs if one factor is a Cayley graph. We use voltage graphs to explore embeddings of various products where one factor is a hypercube, describing some minimal and symmetrical embeddings. We then define a graph product, the weak symmetric difference, and illustrate a voltage graph construction useful for obtaining an embedding of the weak symmetric difference of an arbitrary graph with a hypercube.
20
Vitale, F. "FAST LEARNING ON GRAPHS." Doctoral thesis, Università degli Studi di Milano, 2011. http://hdl.handle.net/2434/155500.
Full textAbstract:
We carry out a systematic study of classification problems on networked data,
presenting novel techniques with good performance both in theory and in
practice.
We assess the power of node classification based on class-linkage information
only. In particular, we propose four new algorithms that exploit the
homiphilic bias (linked entities tend to belong to the same class) in different
ways.
The set of the algorithms we present covers diverse practical needs: some
of them operate in an active transductive setting and others in an on-line
transductive setting. A third group works within an explorative protocol,
in which the vertices of an unknown graph are progressively revealed to the
learner in an on-line fashion.
Within the mistake bound learning model, for each of our algorithms
we provide a rigorous theoretical analysis, together with an interpretation
of the obtained performance bounds. We also design adversarial strategies
achieving matching lower bounds. In particular, we prove optimality for all
input graphs and for all fixed regularity values of suitable labeling complexity
measures. We also analyze the computational requirements of our methods,
showing that our algorithms can to handle very large data sets.
In the case of the on-line protocol, for which we exhibit an optimal algorithm
with constant amortized time per prediction, we validate our theoretical
results carrying out experiments on real-world datasets.
21
Broutin, Nicolas. "Random trees, graphs and recursive partitions." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00842019.
Full textAbstract:
Je présente dans ce mémoire mes travaux sur les limites d'échelle de grandes structures aléatoires. Il s'agit de décrire les structures combinatoires dans la limite des grandes tailles en prenant un point de vue objectif dans le sens où on cherche des limites des objets, et non pas seulement de paramètres caractéristiques (même si ce n'est pas toujours le cas dans les résultats que je présente). Le cadre général est celui des structures critiques pour lesquelles on a typiquement des distances caractéristiques polynomiales en la taille, et non concentrées. Sauf exception, ces structures ne sont en général pas adaptées aux applications informatiques. Elles sont cependant essentielles de part l'universalité de leurs propriétés asymptotiques, prouvées ou attendues. Je parle en particulier d'arbres uniformément choisis, de graphes aléatoires, d'arbres couvrant minimaux et de partitions récursives de domaines du plan:Arbres aléatoires uniformes. Il s'agit ici de mieux comprendre un objet limite essentiel, l'arbre continu brownien (CRT). Je présente quelques résultats de convergence pour des modèles combinatoires ''non-branchants'' tels que des arbres sujets aux symétries et les arbres à distribution de degrés fixée. Je décris enfin une nouvelle décomposition du CRT basée sur une destruction partielle.
Graphes aléatoires. J'y décris la construction algorithmique de la limite d'échel-le des graphes aléatoires du modèle d'Erdös--Rényi dans la zone critique, et je fais le lien avec le CRT et donne des constructions de l'espace métrique limite. Arbres couvrant minimaux. J'y montre qu'une connection avec les graphes aléatoires permet de quantifier les distances dans un arbre convrant aléatoire. On obtient non seulement l'ordre de grandeur de l'espérance du diamètre, mais aussi la limite d'échelle en tant qu'espace métrique mesuré. Partitions récursives. Sur deux exemples, les arbres cadrant et les laminations du disque, je montre que des idées basées sur des théorèmes de point fixe conduisent à des convergences de processus, où les limites sont inhabituelles, et caractérisées par des décompositions récursives.
22
Ehrenmüller, Julia [Verfasser], and Anusch [Akademischer Betreuer] Taraz. "Existence and enumeration of spanning structures in sparse graphs and hypergraphs / Julia Ehrenmüller. Betreuer: Anusch Taraz." Hamburg : Universitätsbibliothek der Technischen Universität Hamburg-Harburg, 2016. http://d-nb.info/111163064X/34.
Full text
23
Ehrenmüller, Julia Verfasser], and Anusch [Akademischer Betreuer] [Taraz. "Existence and enumeration of spanning structures in sparse graphs and hypergraphs / Julia Ehrenmüller. Betreuer: Anusch Taraz." Hamburg : Universitätsbibliothek der Technischen Universität Hamburg-Harburg, 2016. http://nbn-resolving.de/urn:nbn:de:gbv:830-88214628.
Full text
24
Legault, Philippe. "Towards New Bounds for the 2-Edge Connected Spanning Subgraph Problem." Thesis, Université d'Ottawa / University of Ottawa, 2017. http://hdl.handle.net/10393/36202.
Full textAbstract:
Given a complete graph K_n = (V,E) with non-negative edge costs c ∈ R^E, the problem multi-2EC_cost is that of finding a 2-edge connected spanning multi-subgraph of K_n with minimum cost. It is believed that there are no efficient ways to solve the problem exactly, as it is NP-hard. Methods such as approximation algorithms, which rely on lower bounds like the linear programming relaxation multi-2EC^LP of multi-2EC , thus become vital cost cost to obtain solutions guaranteed to be close to the optimal in a fast manner.
In this thesis, we focus on the integrality gap αmulti-2EC of multi-2EC^LP , which is a
measure of the quality of multi-2EC^LP as a lower bound. Although we currently only know cost that 6/5 ≤ αmulti-2EC_cost ≤ 3 , the integrality gap for multi-2EC_cost has been conjectured to be 6/5. We explore the idea of using the structure of solutions for αmulti-2EC_cost and the concept of convex combination to obtain improved bounds for αmulti-2EC_cost. We focus our efforts on a family J of half-integer solutions that appear to give the largest integrality gap for multi-2EC_cost. We successfully show that the conjecture αmulti-2EC_cost = 6/5 is true for any cost functions optimized by some x∗ ∈ J.
We also study the related problem 2EC_size, which consists of finding the minimum size 2-edge connected spanning subgraph of a 2-edge connected graph. The problem is NP-hard even at its simplest, when restricted to cubic 3-edge connected graphs. We study that case in the hope of finding a more general method, and we show that every 3-edge connected cubic graph G = (V ′, E′), with n = |V ′| allows a 2EC_size solution for G of size at most 7n/6 This improves upon Boyd, Iwata and Takazawa’s guarantee of 6n/5 and extend Takazawa’s 7n/6 guarantee for bipartite cubic 3-edge connected graphs to all cubic 3-edge connected graphs.
25
Araujo, João Paulo de. "A communication-efficient causal broadcast publish/subscribe system." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS081.
Full textAbstract:
La Publication/Abonnement (Publish/Subscribe, Pub/Sub) est un paradigme qui permet aux nœuds d'un système distribué de diffuser des informations de manière asynchrone. Cette thèse s'intéresse aux systèmes de Pub/Sub basés sur des sujets (topic-based), en adressant les problèmes de performances et de contention existant dans plusieurs approches reposant sur des arbres. Les solutions proposées utilisent la construction d'arbres couvrants regroupant les abonnés et dont les racines sont les émetteurs. Les arbres associés à différentes sources sont organisés différemment. La première contribution de la thèse propose un protocole de diffusion causal agrégeant des messages et dans lequel aucun temporisateur n'est nécessaire. Le protocole regroupe les messages en un seul message sans utiliser des temporisateurs en tirant parti du délai de livraison supplémentaire imposé à un nœud lorsque les messages sont reçus en dehors de l'ordre causal ainsi que des intersections existantes entre des arbres couvrants. La deuxième contribution est un système de Pub/Sub par sujet, VCube-PS, qui assure l'ordre de traitement causal des messages publiés sur un même sujet et gère efficacement la publication de messages sur des sujets très populaires ("hot topics"). Les résultats des simulations confirment que le protocole d'agrégation causale proposé réduit le trafic réseau ainsi que des latences de livraison, en limitant la contention de messages. Comparé à une approche utilisant un seul arbre par sujet, VCube-PS repartit mieux la charge lors de publications massives sur des "hot topic"The Publish/Subscribe (Pub/Sub) paradigm enables nodes of a distributed system to disseminate information asynchronously. This thesis investigates how to provide a communication-efficient topic-based Pub/Sub system by addressing the problems of traffic overhead and message contention, present in several tree-based solutions. The proposed contributions build distributed spanning trees on top of a hypercube-like topology, such that the source of each message is the root of its own dynamically built spanning tree. Trees rooted at different nodes are differently organized. Initially, it is proposed a causal broadcast protocol which reduces network traffic by aggregating messages without the use of timers. It exploits the causal relation between messages and path intersections between different trees. Different from existing timer-based approaches, it does not increase delivery latency. The second contribution is a topic-based Pub/Sub system, VCube-PS, which ensures causal delivery order for messages published to the same topic and efficiently supports publication of messages to "hot topics'', i.e., topics with high publication rates. Simulation results confirm that the proposed causal aggregation protocol reduces network traffic as well as delivery latencies since there is less message contention. Compared to an approach that uses one single tree per topic, VCube-PS performs better when there is a high publication rate per topic since it provides load balancing of publication
26
Chang, Chung-Haw, and 張仲浩. "Spanning Container on Variations of Hypercubes." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/36023865327749994571.
Full textAbstract:
博士國立中央大學
數學研究所
94
Let G be a graph with connectivity κ(G). It follows from Menger's Theorem that there are k vertex-disjoint paths joining any two distinct vertices when k ≦κ(G). A k -container C ( u, v) of a graph G is a set of k vertex-disjoint paths between u and v. A k-container is a k*-container if it contains all vertices of G . A graph G is k*-connected if there exists a k*-container between any two vertices. A graph G is super spanning connected if G is k*-connected for every 1 ≦ k ≦κ(G). However, we need some modification as we study bipartite k-connected graphs. A bipartite graph G is k*-laceable if there exists a k*-container between any two vertices from different partite sets. A bipartite graph G is super spanning laceable if G is k*-laceable for 1 ≦ k ≦ κ(G). A k*-container C ( u, v) ={ P1, … , Pk } is equitable if | | Pi | - | Pj | | ≦ 2, 1 ≦ i , j ≦ k. The hypercube Qn is one of the most popular networks. In this thesis, we will discuss that the spanning connectivity, the spanning laceability, and related problems of hypercube Qn, folded hypercube FQn, and enhanced hypercube Qn,m.
27
you, yie yiesh, and 游郁樞. "spanning trees of graphs." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/92233158955795216599.
Full text
28
Lin, Yao-Chung, and 林耀鐘. "Two Spanning Disjoint Paths with Required Length in Generalized Hypercubes." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/96119395822388040174.
Full textAbstract:
碩士國立暨南國際大學
資訊工程學系
99
This work investigates 2RP-property of a generalized hypercube G. Given any four distinct vertices u, v, x and y in G, let l1 and l2 be two integers such that l1 (l2) is not less than the distance between u and v (x and y), and l1+l2 is equal to the number of vertices in G minus two. Then, there exist two vertex-disjoint paths P1 and P2 such that (1) P1 is a path joining u and v with length of l1; (2) P2 is a path joining x and y with length of l2, and (3) P1 or P2 spans G except some special conditions. This work shows that a r-dimensional generalized hypercube, denoted by G(m_r, m_{r-1}, …, m_1), satisfies 2RP-property, where mi³4 for all 1£i£r.
29
Liu, Yi-Jiun, and 劉宜君. "Constructing independent spanning trees for hypercubes and locally twisted cubes." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/20919339127141912268.
Full textAbstract:
碩士國立交通大學
應用數學系所
97
The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages such as the increase of fault-tolerance and bandwidth. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. In [27], Zehavi and Itai stated two versions of the n independent spanning trees conjecture. The vertex (edge) conjecture is that any n-connected ($n$-edge-connected) graph has n vertex-ISTs (edge-ISTs) rooted at an arbitrary vertex r. In [16], Khuller and Schieber proved that the vertex conjecture implies the edge conjecture. Recently, in [12], Hsieh and Tu proposed an algorithm to construct n edge-ISTs rooted at vertex 0 for an n-dimensional locally twisted cube, which is a variant of the hypercube. Since the locally twisted cube is it not vertex-transitive, Hsieh and Tu's result does not solve the edge conjecture for the locally twisted cube. In the thesis, we confirm the vertex conjecture (and hence also the edge conjecture) for the locally twisted cube by proposing an algorithm to construct $n$ vertex-ISTs rooted at any vertex for the n-dimensional locally twisted cube. We also confirm the vertex conjecture (and hence also the edge conjecture) for the hypercube.
30
許雅綾. "Connected Dominating Set of Hypercubes and Star Graphs." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/82374709531160994459.
Full textAbstract:
碩士明新科技大學
資訊管理研究所
100
In wired or wireless networks, routing efficiently among immobile or mobile devices is an important issue. A connected dominating set (CDS) brings benefits to network routing. The CDS can be served as a virtual backbone of a network, and it always adapted easily to new network topology. A virtual backbone is a set of vertices which can help with routing. Any vertex outside the virtual backbone can send messages or signals to another vertex through the virtual backbone. So the virtual backbone has great benefits to routing and management of networks. We may impose a virtual backbone to support shortest path routing, fault-tolerant routing, multi-casting, and radio broadcasting, etc. Recently, there are many researches of the CDS on wireless networks are discussed, but only a few researches on wired networks are discussed. Both hypercubes and star graphs are recursively constructed graphs, they have lots of attractive topologies, such as vertex-symmetry, edge-symmetry, and easy routing. In this paper, we focus on constructing the minimum CDS (MCDS) of n-dimensional hypercubes and n-dimensional star graphs.
31
Shih-Jung, Wu. "Fault-tolerant Simulation of a Class of Regular Graphs in Hypercubes and Incrementally Extensible Hypercubes." 2006. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0002-0706200601030000.
Full text
32
Wu, Shih-Jung, and 武士戎. "Fault-tolerant Simulation of a Class of Regular Graphs in Hypercubes and Incrementally Extensible Hypercubes." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/68350016588012720764.
Full textAbstract:
博士淡江大學
資訊工程學系博士班
94
The hypercube is a widely-used interconnection architecture in the parallel machine. The Incrementally Extensible Hypercube (IEH), which is derived from the hypercube, is a generalization of interconnection network. Unlike the hypercube, the IEH can be constructed for any number of nodes. In other words, the IEH is incrementally expandable. In this thesis, the problem of embedding and reconfiguring some regular structures is considered in an IEH with faulty nodes. In recent years, the Fibonacci cube is a new interconnection architecture derived from hypercube. It also has some properties differ from hypercube. Thus we discuss the embedding of Fibonacci cube into the faulty hypercube. Some fault-tolerant embedding algorithms are proposed in this thesis. First, the algorithm in the present study enables us to obtain the good embedding of a ring into a faulty IEH with 2-expansion. Such result can be tolerated up to (n+1) faults with congestion 1, load 1, and dilation 3. When we allow unbounded expansion, the result of embedding of a ring into a faulty IEH can be tolerated up to O(n*log2m) faults with congestion 1, load 1, and dilation 4. The embedding methods in the study are mainly optimized for balancing the processor loads, under the situation of minimizing dilation and congestion as far as possible. Next we consider embedding of mesh into faulty IEH. In 2-expansion, it can be tolerated (n+1) faults with dilation 3, congestion 1, and load 1. Moreover, it can be tolerated up to O(n2-(r+s)2) in unbounded expansion. We discuss embedding of a complete binary tree into faulty IEH in the third. The cost is dilation 4, congestion 1, and load 1. In 2-expansion and unbounded expansion, embedding of a complete binary tree into faulty IEH can be tolerated (n+1) and O(n2-h2) faults. Finally, embedding of Fibonacci cube into faulty hypercube with dilation 3, congestion 2, load 1, unbounded expansion and O(m2-n2) faults can be tolerated, induced by our algorithm.
33
Ko, Tsz-Mei. "On the VLSI decompositions for complete graphs, DeBruijn graphs, hypercubes, hyperplanes, meshes, and shuffle-exchange graphs." Thesis, 1993. https://thesis.library.caltech.edu/3284/1/Ko_tm_1993.pdf.
Full textAbstract:
A C-chip VLSI decomposition of a graph G is a collection of C vertex-disjoint subgraphs of G which together contain all of G's vertices and a subset of its edges. If the vertex-disjoint subgraphs are isomorphic to each other, we call one of these isomorphic subgraphs a building block. The efficiency of a VLSI decomposition is defined to be the fraction of edges of G that are in the subgraphs. In this thesis, motivated by the need to construct large Viterbi decoders, we study VLSI decompositions for deBruijn graphs. We obtain some strong necessary conditions for a graph to be a building block for a deBruijn graph, and some slightly more restrictive sufficient conditions which allow us to construct some efficient building blocks for deBruijn graphs. By using the methods described in this thesis, we have found a 64-chip VLSI decomposition of the deBruijn graph B13 with efficiency 0.754. This decomposition is being used by JPL design engineers to build a single-board Viterbi decoder for the K = 15, rate 1/4 convolutional code which will be used on NASA's Galileo mission.
Furthermore, we study VLSI decompositions for the families of complete graphs, hypercubes, hyperplanes, meshes, and shuffle-exchange graphs. In each of these cases, we obtain very efficient or even optimal decompositions. We also prove several general theorems that can be applied to obtain bounds on the efficiencies for VLSI decompositions of other complex graphs. In general, the results presented in this thesis are useful for implementing massively parallel computers.
34
MengYu-Lin and 林孟玉. "Independent Spanning Trees on Recursive Circulant Graphs." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/94651256289912105016.
Full textAbstract:
碩士國立臺灣科技大學
資訊管理系
91
Two spanning trees of a given graph G = (V, E) are said to be independent if they are rooted at the same vertex, say r, and for each vertex v Î V\{r} the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees of G is said to be independent if they are pairwise independent. Zehavi and Itai conjectured that any k-connected graph has k independent spanning trees rooted at an arbitrary vertex. This conjecture is still open for k > 3. Broadcasting in a distributed system is the message dissemination from a source node to every other node in the system. We can design a fault-tolerant broadcasting scheme based on independent spanning trees of a network. The fault-tolerance can be achieved by sending k copies of the message along k independent spanning trees rooted at the source node. The recursive circulant graph was proposed by Park and Chwa in 1994. Let G(cdm,d) denote a recursive circulant graph. Then G has N=cdm vertices, where 0
35
Smith, Jacqueline. "Minimum Degree Spanning Trees on Bipartite Permutation Graphs." Master's thesis, 2011. http://hdl.handle.net/10048/1900.
Full textAbstract:
The minimum degree spanning tree problem is a widely studied NP-hard variation of the minimum spanning tree problem, and a generalization of the Hamiltonian path problem. Most of the work done on the minimum degree spanning tree problem has been on approximation algorithms, and very little work has been done studying graph classes where this problem may be polynomial time solvable. The Hamiltonian path problem has been widely studied on graph classes, and we use classes with polynomial time results for the Hamiltonian path problem as a starting point for graph class results for the minimum degree spanning tree problem. We show the minimum degree spanning tree problem is polynomial time solvable for chain graphs. We then show this problem is polynomial time solvable on bipartite permutation graphs, and that there exist minimum degree spanning trees of these graphs that are caterpillars, and that have other particular structural properties.
36
Huang, Kuo-Chen, and 黃國禎. "Embedded Congestion-Free Spanning Trees in Arrangement Graphs." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/69342281283130315994.
Full textAbstract:
碩士逢甲大學
資訊工程學系
88
The n-star graph has been shown as an attractive alternative to the widely used hypercube. Like hypercube, the star graph possesses regular structure, node symmetry, edge symmetry, hierarchical structure and maximally fault-tolerant capabilities. It has significant advantages over the hypercube, such as a lower degree and a smaller diameter. However, a major practical difficulty with the n-star graph is that the restriction on the number of nodes: n! for an n-star graph. Since there is a large gap between n! and (n+1)!, one may face the choice of either too few or too many available nodes. Recently, the arrangement graph has been proposed to solve the problem of star graphs. It is a generalization of the star graph (n-k=1), and preserves most of the excellent properties of the star graph. To find edge-disjoint spanning trees is an important issue in the interconnection networks. The more edge-disjoint spanning trees we have, the more bandwidth we can used. Moreover, it can support the fault tolerant broadcasting. In this thesis, we propose an algorithm to construct edge-disjoint spanning trees in . First, we construct n edge-disjoint spanning trees for , and prove their height is optimal. The result is better than Chen’s [10]. Then we show how to obtain maximum edge-disjoint spanning trees with optimal height for .
37
Tsai, Chang-Hsiung, and 蔡正雄. "Fault-tolerant hamiltonian properties on butterflies, recursive circulant graphs, and hypercubes." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/12055600187371514451.
Full textAbstract:
博士國立交通大學
資訊科學系
90
The performance of a distributed system is significantly determined by its network topology. Designing the topology of interconnection network involves mutually conflicting requirements. One of the major requirements in designing the topology of networks is the hamiltonicity. On the other hand, fault tolerance is highly desirable for massive parallel systems which have relative high probability of failure. For a positive integer k, a graph G = (V,E) is k-hamiltonian if G-F is hamiltonian for any F Í VÈE with |F| £ k. A k-hamiltonian graph G is optimal if it contains the least number of edges among all k-hamiltonian graphs with the same number of vertices as G. The study of optimal k-hamiltonian graphs is motivated from the design of optimal fault-tolerant token rings in computer networks. This research studied fault-tolerant hamiltonicities of three famous family interconnection networks, namely wrapped butterfly graphs, recursive circulant graphs, and hypercubes. In this thesis, F denotes the fault set of the graph and fv denotes the number of faulty node in F. When the hamiltonicity of a graph G is concerned, it is usual to investigate whether G is hamiltonian or hamiltonian-connected. Since a bipartite graph is not hamiltonian-connected, Simmons[35] introduced the concept of hamiltonian laceability for class of bipartite graphs. It is known that every hypercube Qn is a bipartite graph. Assume that n ³ 2 and F is a subset of edges with |F| £ n-2. We prove that there exists a hamiltonian path in Qn -F between any two vertices of different partite sets. Moreover, there exists a path of length 2n-2 between any two vertices of the same partite set. Assume that n ³ 3 and |F| £ n-3. We prove that there exists a hamiltonian path in Qn-{v}-F between any two vertices in the partite set without node v. In addition, it is shown that Qn contains every even cycle even if it has n-2 edge faults. Let BFn denote the n-dimensional wrapped butterfly graph with n2n vertices. When |F| £ 2, we prove that BFn-F contains a cycle of length n2n-2fv. Moreover, BFn-F contains a cycle of length n2n-fv if n is an odd integer. In other words, BFn is optimal 2-hamiltonian regular graph if n is an odd integer. A recursive circulant graph G(cdk,d) is a circulant graph with cdk vertices and jumps of powers of d where d ³ 2 and 2£c£d. We also prove that G(cdk,d)-F remains hamiltonian when it is not a bipartite graph and |F| £ deg(G(cdk,d))-2, where deg(G(cdk,d)) denotes a degree of G(cdk,d). Moreover, we prove that for any two vertices u and v in V(G(cdk,d))-F, there exists a hamiltonian path of G(cdk,d)-F joining u and v, when it is not a bipartite graph and |F| £ deg(G(cdk,d))-3. Furthermore, all bounds are tight.
38
Lin, Chung-Ming, and 林仲銘. "Balancing Minimum Spanning Trees and Multiple-Source Minimum Routing Cost Spanning Trees on Metric Graphs." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/39149250907379405520.
Full text
39
Yu, Li-ping, and 于立斌. "On The Spanning Connectivity of the Burnt Pancake Graphs." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/9g5vwu.
Full textAbstract:
碩士靜宜大學
資訊工程學系碩士班
98
Let u and v be any two distinct vertices of an undirected graph G, which is k-connected. For 1w k, a w-container C(u,v) of a k-connected graph G is a set of w-disjoint paths joining u and v. A w-container C(u,v) of G is a w*-container if it contains all the vertices of G. A graph G is w*-connected if there exists a w*-container between any two distinct vertices. Let κ(G) be the connectivity of G. A graph G is super spanning connected if G is i*-connected for 1iκ(G).In this thesis, we prove that the n-dimensional burnt pancake graph Bn is super spanning connected if and only if n≠2.
40
Xiao-QiangChen and 陳小強. "Constructing Independent Spanning Trees on (n,k)-Star Graphs." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/rjh72w.
Full text
41
Yuan-Jiunn, Wang, and 王元俊. "Canonical Spanning Trees for Planar Graphs with Application to Graph Encoding." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/39131628092351097801.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
87
Let G be an n-node m-edge planar graph that may contain multiple edges. We show that there exists an encoding code(G) of G such that (1) code(G) has 2m+3n+o(m+n) bits; (2) code(G) can be obtained from G in O(m+n^2) time; (3) G can be decoded from code(G) in O(m+n) time; (4) the degree of a node in G can be answered from code(G) in O(1) time; and (5) whether two nodes are adjacent in G can be answered from code(G) in O(1) time. Moreover, if G is not allowed to contain multiple edges, then the bit count of code(G) can be reduced to 2m+2n+o(n). Our results are based on computing an embedding of G that contains a canonical spanning tree. Our results reduce the bit counts of the encodings of Chuang, Garg, He, Kao, and Lu. For a G that may (respectively, may not) contain multiple edges, the code(G) of Chuang et al. has 2m+5n+o(m+n) (respectively, 1.66m+5n+o(n)) bits, for any positive constant $k$. However, their code(G) can be obtained from G in O(m+n) time.
42
Lin, Yen-Yi. "A Study of the Spanning Star Forest Problem on Bipartite Graphs." 2008. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0001-0108200811152500.
Full text
43
Liu, Yi-Jin, and 呂宜錦. "The Interchange Graphs of Non-isomorphic Tournaments with Minimum Score Vectors Are Exactly Hypercubes." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/35478602496317352048.
Full textAbstract:
碩士國立臺北商業技術學院
資訊與決策科學研究所
99
A tournament of size n, denoted by Tn, represents the players p1,p2,...,pn in a round robin tournament and every two distinct players pi and pj compete exactly one game to decide the winner (and the loser) between them and tie is not permitted. If pi beats pj, we write pi→pj. The score of a player pi in a tournament, denoted si, is the number of players beaten by pi, and the score sequence of Tn is a non-decreasing order list of scores of all players, denote by Sn=(s1,s2,...,sn). Let T(Sn) be the collection of tournaments that realize a given score sequence Sn. A tournament is called strong if there exist directed paths for each of a pair of vertices. A score sequence Sn is said to be strong if there is a strong tournament in T(Sn). In a strong tournament Tn with score sequence Sn=(s1,s2,...,sn), Moon shows that there has exactly C(n,3)-Σ(i=1 to n)C(si,2) (directed) cycles of length 3, for short a 3-cycles. A △-interchange is a transformation which reverses the orientations of the arcs in the 3-cycle of a tournament. An interchange graph is an undirected graph whose vertices are the tournaments in T(Sn) and an edge joins two vertices (tournaments) if they can be transformed to each other by a △-interchange. Chen et al., in 2009, shown that the interchange graphs of tournaments with score sequence Ŝn=(1,1,2,...,n-3,n-2,n-2) are hypercubes with dimension n-2. They studied in the case when the vertices of the tournaments were labeled. If the label removed, some of the tournaments can be regarded as the same. In general, two tournaments are said to be isomorphic if there is a one-to-one correspondence between their vertices and edges such that incidences are preserved. In this thesis, we prove that the interchange graph of non-isomorphic tournaments with the same score sequence Ŝn can be hypercube Qn-4.
44
Chen, Ya-Chi, and 陳雅琪. "Embedding the Maximum Number of Congestion-Free Spanning Trees in Arrangement Graphs." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/20973566596347105767.
Full textAbstract:
碩士逢甲大學
資訊工程學系
89
It has been shown that the star graph is superior to the widely used hypercube, such as smaller degree, diameter, and average distance. However, a major practical difficulty of the star graph is its restriction on the number of nodes. The (n,k)-arrangement graph is a generalized version of star graphs that overcomes the restriction of the star graph on number nodes, and preserves many attractive properties of star graphs, such as regular structure, vertex symmetry, edge symmetry, hierarchical structure, and maximally fault-tolerance, etc. It is a good interconnection network. The broadcasting is an important issue in interconnection networks. To establish the basic infrastructure of network broadcasting is to find the spanning trees of the network. Once we can discover large number of congestion-free spanning trees in a network, these spanning trees can be utilized to balance network transmission for reducing congestion, to increase parallel processing capability for augmenting broadcasting performance, and to raise fault tolerance capability for maintaining network reliability. Besides, the lower the height of each spanning tree is, the less the delay of the network is. Therefore, obtaining more and congestion-free spanning trees with lower height in a network is crucial to network broadcasting. In this thesis, a methodology to embed all (k(n-k)) congestion-free spanning trees in an (n,k)-arrangement graph is proposed. Then, we show that the height of each spanning tree is optimal , for k>=2/n , and is less and equal to the optimal value plus one, for k<2/n .
45
Lo, Wei-Chun, and 羅尉駿. "An Efficient Algorithm for the Robustest Spanning Tree Problem on Interval Graphs." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/46393349617000557898.
Full textAbstract:
碩士國立東華大學
資訊工程學系
103
Let T = (V,F) be a spanning tree of a graph G = (V,E). For an edgee∊E\F , let num(e) = |C|-1 where C is the cycle by adding e to T. In this thesis, we consider the robustest spanning tree problem. This problem is to find a spanning tree such that R(T) =∑_(e∊E \F)▒〖num(e)〗is smallest among all possible spanning trees of G. We propose an algorithm for solving this problem on interval graphs in O(n^6), where n = |V|
46
Kuo, Chi-Jung, and 郭啟容. "On the Study of Feedback Problems and Independent Spanning Trees in Cayley Graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/07750723911737262248.
Full textAbstract:
博士國立臺灣科技大學
資訊管理系
98
Rotator graph and trivalent Cayley graph are two members of Cayley graphs. This dissertation studies the minimum feedback vertex/arc set in rotator and incomplete rotator graphs, as well as the independent spanning trees of trivalent Cayley graphs. A feedback vertex/arc set (abbreviated as FVS/FAS) of a graph is a subset of the vertices/arcs which contains at least one vertex/arc for every cycle of the graph. Removing the FVS/FAS from the graph makes the remaining graph acyclic. A minimum FVS/FAS is an FVS/FAS which contains the smallest number of vertices/arcs. For a rotator graph with M = n! nodes, Hsu and Lin [22] first proposed an algorithm which constructed an FVS with time complexity O(nn-3). In addition, they found that the size of the FVS is M /3, which was proved to be minimum. In this dissertation, we present an efficient algorithm which constructs an FVS for a rotator graph in O(M) time and also obtains the minimum FVS size M /3. In other words, this algorithm derives the optimal result with the time complexity which is linearly proportional to the number of nodes in the rotator graph. In addition, we present a concise formula for finding an FAS for a rotator graph and prove that the FAS is minimum. This formula can be easily implemented by an efficient algorithm which obtains a minimum FAS in a rotator graph. Finally, we also present a concise formula for finding a minimum FAS in an incomplete rotator graph in this dissertation. The construction of multiple independent spanning trees has many applications in network communication, such as fault-tolerant broadcasting and secure message distribution. Cheriyan and Maheshwari [8] showed that three independent spanning trees can be constructed in O(|V||E|) time for every 3-connected graph. In this dissertation, we present a linear time algorithm to construct three independent spanning trees rooted at any node in a trivalent Cayley graph, which was proposed by Vadapalli and Srimani in [38] for designing the topology of an interconnection network with constant regularity of node degree 3. In particular, our algorithm relies on a set of concise rules that describe the parent of nodes in each tree. Therefore, the construction scheme can be easily parallelized.
47
Chang, Jui-Yuan, and 張睿元. "A Study of Minimum Vertex Ranking Spanning Tree Problem on Some Classes of Graphs." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/5hbbp9.
Full textAbstract:
碩士國立東華大學
資訊工程學系
96
A vertex ranking of a graph G is a labeling of the vertices of G with positive integers such that every path between two vertices with the same label i contains a vertex with label j > i. A vertex ranking is minimum if the largest rank k in it is the smallest among all possible vertex rankings of G. This rank is denoted by rank(G). The minimum vertex ranking problem is to find a minimum vertex ranking of G. The minimum vertex ranking spanning tree problem on G is to find a spanning tree T of G such that rank(T) is minimum among all possible spanning trees of G. It is known that the problem is NP-Hard for general graphs. There are polynomial-time algorithms on interval graphs, permutation graphs, outerplanar graphs, and series-parallel graphs. In this thesis, we study the minimum vertex ranking spanning tree problem on the classes of interval graphs, split graphs, and cographs. We show that this problem on these classes of graphs can be solved in linear time. It improves a previous result that runs in O(n^3) time on interval graphs where n is the number of vertices in the input graph.
48
Li, Chen Yu, and 李琛瑜. "An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/53792569248327718938.
Full text
49
LI, YU-QI, and 李育奇. "Finding the most vital edge with respect to minimum spanning tree in weighted graphs." Thesis, 1991. http://ndltd.ncl.edu.tw/handle/63797462570157233444.
Full text
50
JIN, DIAO-MING, and 金道銘. "Finding the most vital edge with respect to minimum spanning trees in weighted graphs." Thesis, 1992. http://ndltd.ncl.edu.tw/handle/42694468948600483850.
Full text