Relevant bibliographies by topics / K - connected graphs

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers

Academic literature on the topic 'K - connected graphs'

Author: Grafiati
Published: 4 June 2021
Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'K - connected graphs.'

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.

Journal articles on the topic "K - connected graphs"

1

CHENG, EDDIE, and MARC J. LIPMAN. "UNIDIRECTIONAL (n, k)-STAR GRAPHS." Journal of Interconnection Networks 03, no. 01n02 (March 2002): 19–34. http://dx.doi.org/10.1142/s0219265902000525.

Full text
Abstract:
Arrangement graphs14 and (n, k)-star graphs11 were introduced as generalizations of star graphs1. They were introduced to provide a wider set of choices for the order of topologically attractive interconnection networks. Unidirectional interconnection networks are more appropriate in many applications. Cheng and Lipman5, and Day and Tripathi17 studied the unidirectional star graphs, and Cheng and Lipman7 studied orientation of arrangement graphs. In this paper, we show that every (n, k)-star graph can be oriented to a maximally arc-connected graph when the regularity of the graph is even. If the regularity is odd, then the resulting directed graph can be augmented to a maximally arc-connected directed graph by adding a directed matching. In either case, the diameter of the resulting directed graph is small. Moreover, there exists a simple and near-optimal routing algorithm.
APA, Harvard, Vancouver, ISO, and other styles
2

Ando, Kiyoshi, and Yoko Usami. "Critically (k, k)-connected graphs." Discrete Mathematics 66, no. 1-2 (August 1987): 15–20. http://dx.doi.org/10.1016/0012-365x(87)90114-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Marhelina, Sally. "RAINBOW CONNECTION PADA GRAF k -CONNECTED UNTUK k = 1 ATAU 2." Jurnal Matematika UNAND 2, no. 1 (March 10, 2013): 78. http://dx.doi.org/10.25077/jmu.2.1.78-84.2013.

Full text
Abstract:
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of aconnected graph G, denoted by rc(G) is the smallest number of colors needed such thatG is rainbow connected. In this paper, we will proved again that rc(G) ≤ 3(n + 1)/5 forall 3-connected graphs, and rc(G) ≤ 2n/3 for all 2-connected graphs.
APA, Harvard, Vancouver, ISO, and other styles
4

Mynhardt, C. M., L. E. Teshima, and A. Roux. "Connected k-dominating graphs." Discrete Mathematics 342, no. 1 (January 2019): 145–51. http://dx.doi.org/10.1016/j.disc.2018.09.006.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Hong, Zhen-Mu, Zheng-Jiang Xia, Fuyuan Chen, and Lutz Volkmann. "Sufficient Conditions for Graphs to Be k -Connected, Maximally Connected, and Super-Connected." Complexity 2021 (February 22, 2021): 1–11. http://dx.doi.org/10.1155/2021/5588146.

Full text
Abstract:
Let G be a connected graph with minimum degree δ G and vertex-connectivity κ G . The graph G is k -connected if κ G ≥ k , maximally connected if κ G = δ G , and super-connected if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we present sufficient conditions for a graph with given minimum degree to be k -connected, maximally connected, or super-connected in terms of the number of edges, the spectral radius of the graph, and its complement, respectively. Analogous results for triangle-free graphs with given minimum degree to be k -connected, maximally connected, or super-connected are also presented.
APA, Harvard, Vancouver, ISO, and other styles
6

Hennayake, Kamal, Hong-Jian Lai, Deying Li, and Jingzhong Mao. "Minimally (k, k)-edge-connected graphs." Journal of Graph Theory 44, no. 2 (September 9, 2003): 116–31. http://dx.doi.org/10.1002/jgt.10132.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Shen, Yuanyuan, Xinhui An, and Baonyindureng Wu. "Hamilton-Connected Mycielski Graphs∗." Discrete Dynamics in Nature and Society 2021 (September 15, 2021): 1–7. http://dx.doi.org/10.1155/2021/3376981.

Full text
Abstract:
Jarnicki, Myrvold, Saltzman, and Wagon conjectured that if G is Hamilton-connected and not K 2 , then its Mycielski graph μ G is Hamilton-connected. In this paper, we confirm that the conjecture is true for three families of graphs: the graphs G with δ G > V G / 2 , generalized Petersen graphs G P n , 2 and G P n , 3 , and the cubes G 3 . In addition, if G is pancyclic, then μ G is pancyclic.
APA, Harvard, Vancouver, ISO, and other styles
8

Karpov, D. V. "Blocks in k-connected graphs." Journal of Mathematical Sciences 126, no. 3 (March 2005): 1167–81. http://dx.doi.org/10.1007/s10958-005-0084-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Egawa, Yoshimi. "k-shredders ink-connected graphs." Journal of Graph Theory 59, no. 3 (November 2008): 239–59. http://dx.doi.org/10.1002/jgt.20336.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Devillers, Alice, Joanna B. Fawcett, Cheryl E. Praeger, and Jin-Xin Zhou. "On k-connected-homogeneous graphs." Journal of Combinatorial Theory, Series A 173 (July 2020): 105234. http://dx.doi.org/10.1016/j.jcta.2020.105234.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "K - connected graphs"

1

Randby, Scott P. "Embedding K? in 4-connected graphs /." The Ohio State University, 1991. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487759055158486.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Revoori, Soundarya. "Computing the Rectilinear Crossing Number of K." Scholar Commons, 2017. http://scholarcommons.usf.edu/etd/6936.

Full text
Abstract:
Rectilinear crossing number of a graph is the number of crossing edges in a drawing with all straight line edges. The problem of drawing an n-vertex complete graph such that its rectilinear crossing number is minimum is known to be an NP-Hard problem. In this thesis, we present a heuristic that attempts to achieve the theoretical lower bound value of the rectilinear crossing number of a n+1 vertex complete graph from that of n vertices. Our algorithm accepts an optimal or near-optimal rectilinear drawing of Kn graph as input and tries to place a new node such that the crossing number is minimized. Based on prior optimal drawings of Kn, we make an empirical observation that the optimal drawings are triangular in shape. The proposed heuristic has three steps: (1) Given the optimal or near-optimal drawing of Kn, the outer triangle is determined; (2) A set of candidate positions for the (n+1)th node is determined by ensuring none of them are collinear with two or more nodes in the graph; and (3) the best drawing with least rectilinear crossing number is chosen based on the drawings corresponding to the candidate position. A loose bound on the worst-case time complexity of the proposed algorithm is O(n7). The heuristic is not guaranteed to yield optimal solution as the search space is constrained by the input graph. In our experimental results, we obtained optimal results for complete graphs of up to n=27.
APA, Harvard, Vancouver, ISO, and other styles
3

Huang, Peng. "Spectral radius and signless Laplacian spectral radius of k-connected graphs /Huang Peng." HKBU Institutional Repository, 2016. https://repository.hkbu.edu.hk/etd_oa/373.

Full text
Abstract:
The adjacency matrix of a graph is a (0, 1)-matrix indexed by the vertex set of the graph. And the signless Laplacian matrix of a graph is the sum of its adjacency matrix and its diagonal matrix of vertex degrees. The eigenvalues and the signless Laplacian eigenvalues of a graph are the eigenvalues of the adjacency matrix and the signless Laplacian matrix, respectively. These two matrices of a graph have been studied for several decades since they have been applied to many research field, such as computer science, communication network, information science and so on. In this thesis, we study k-connected graphs and focus on their spectral radius and signless Laplacian spectral radius. Firstly, we determine the graphs with maximum spectral radius among all k-connected graphs of fixed order with given diameter. As we know, when a graph is regular, its spectral radius and signless Laplacian spectral radius can easily be found. We obtain an upper bound on the signless Laplacian spectral radius of k-connected irregular graphs. Finally, we give some other results mainly related to the signless Laplacian matrix.
APA, Harvard, Vancouver, ISO, and other styles
4

Hippchen, Thomas. "Intersections of Longest Paths and Cycles." Digital Archive @ GSU, 2008. http://digitalarchive.gsu.edu/math_theses/53.

Full text
Abstract:
It is a well known fact in graph theory that in a connected graph any two longest paths must have a vertex in common. In this paper we will explore what happens when we look at k - connected graphs, leading us to make a conjecture about the intersection of any two longest paths. We then look at cycles and look at what would be needed to improve on a result by Chen, Faudree and Gould about the intersection of two longest cycles.
APA, Harvard, Vancouver, ISO, and other styles
5

Scheder, Dominik Alban. "Approaches to approximating the minimum weight k-edge connected spanning subgraph of a mixed graph." Diss., Connect to online resource, 2005. http://wwwlib.umi.com/cr/colorado/fullcit?p1425760.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Bruno, Nicholas J. "A Sufficient Condition for Hamiltonian Connectedness in Standard 2-Colored Multigraphs." Miami University / OhioLINK, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=miami1438385443.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Sinclair, Phillip Andrew. "Strong snarks and circuit covers, the existence of a circuit in a graph from which we can delete some edges and leave a k-connected graph, for 1#<=#k#<=#3." Thesis, Goldsmiths College (University of London), 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.394495.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Bensmail, Julien. "Partitions et décompositions de graphes." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0062/document.

Full text
Abstract:
Cette thèse est dédiée à l’étude de deux familles de problèmes de partition de graphe. Nous considérons tout d’abord le problème de sommet-partitionner un graphe en sous-graphesconnexes. Plus précisément, étant donnés p entiers positifs n1; n2; :::; np dont la somme vautl’ordre d’un graphe G, peut-on partitionner V (G) en p parts V1; V2; :::; Vp de sorte que chaque Vi induise un sous-graphe connexe d’ordre ni ? Nous nous intéressons ensuite à des questions plus fortes. Que peut-on dire si l’on souhaite que G soit partitionnable de cette manière quels que soient p et n1; n2; :::; np ? Si l’on souhaite que des sommets particuliers de G appartiennent à des sous-graphes particuliers de la partition ? Et si l’on souhaite que les sous-graphes induits soient plus que connexes ? Nous considérons toutes ces questions à la fois du point de vue structurel (sous quelles conditions structurelles une partition particulière existe-t-elle nécessairement ?) et algorithmique (est-il difficile de trouver une partition particulière ?).Nous nous intéressons ensuite à la 1-2-3 Conjecture, qui demande si tout graphe G admet une 3-pondération voisin-somme-distinguante de ses arêtes, i.e. une 3-pondération par laquelle chaque sommet de G peut être distingué de ses voisins en comparant uniquement leur somme de poids incidents. Afin d’étudier la 1-2-3 Conjecture, nous introduisons notamment la notionde coloration localement irrégulière d’arêtes, qui est une coloration d’arêtes dont chaque classe de couleur induit un sous-graphe dans lequel les sommets adjacents sont de degrés différents.L’intérêt principal de cette coloration est que, dans certaines situations, une pondération d’arêtes voisin-somme-distinguante peut être déduite d’une coloration d’arêtes localement irrégulière. Nospréoccupations dans ce contexte sont principalement algorithmiques (est-il facile de trouver une pondération d’arêtes voisin-somme-distinguante ou une coloration d’arêtes localement irrégulière utilisant le plus petit nombre possible de poids ou couleurs ?) et structurelles (quel est le plus petit nombre de couleurs d’une coloration d’arêtes localement irrégulière ?). Nous considérons également ces questions dans le contexte des graphes orientés
This thesis is dedicated to the study of two families of graph partition problems.First, we consider the problem of vertex-partitioning a graph into connected subgraphs.Namely, given p positive integers n1; n2; :::; np summing up to the order of some graph G, canwe partition V (G) into p parts V1; V2; :::; Vp so that each Vi induces a connected subgraph withorder ni? We then consider stronger questions. Namely, what if we want G to be partitionablewhatever are p and n1; n2; :::; np? What if we also want specific vertices of G to belong to somespecific subgraphs induced by the vertex-partition? What if we want the subgraphs induced bythe vertex-partition to be more than connected? We consider all these questions regarding boththe structural (are there structural properties ensuring that a specific vertex-partition necessarilyexists?) and algorithmic (is it hard to deduce a specific vertex-partition?) points of view.Then, we focus on the so-called 1-2-3 Conjecture, which asks whether every graph G admitsa neighbour-sum-distinguishing 3-edge-weighting, i.e. a 3-edge-weighting by which all adjacentvertices of G get distinguished by their sums of incident weights. As a tool to deal with the1-2-3 Conjecture, we notably introduce the notion of locally irregular edge-colouring, which isan edge-colouring in which every colour class induces a subgraph whose adjacent vertices havedistinct degrees. The main point is that, in particular situations, a neighbour-sum-distinguishingedge-weighting of G can be deduced from a locally irregular edge-colouring of it. Our concernsin this context are mostly algorithmic (can we easily find a neighbour-sum-distinguishing edgeweightingor locally irregular edge-colouring using the least number of weights or colours?) andstructural (what is the least number of colours in a locally irregular edge-colouring?). We alsoconsider similar matters in the context of oriented graphs
APA, Harvard, Vancouver, ISO, and other styles
9

Mahjoub, Meriem. "The Survivable Network Design Problems with High Node-Connectivity Constraints : Polyhedra and Algorithms." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED046/document.

Full text
Abstract:
Dans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB
Given a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results
APA, Harvard, Vancouver, ISO, and other styles
10

Lyu, Yu-Han, and 呂昱翰. "Random Generating k-connected Graphs." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/21237074229415401785.

Full text
Abstract:
碩士
國立清華大學
資訊工程學系
95
Enumerating combinatorial objects is an important research topic in combinatorics. Algorithms for random generating combinatorial objects are called sampling. Sampling has many applications in computer science, for example program testing. Mathematicians can use sampling to verify combinatorial property. We developed a simple algorithm to sample k-connected graphs based on Markov Chain Monte Carlo method. This algorithm generates graphs at approximately uniform distribution, and we prove it is rapidly mixing
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "K - connected graphs"

1

Breeding, Ken. Connected and respected: Lessons from the Resolving Conflict Creatively Program, grades K-2. Cambridge, MA: Educators for Social Responsibility, 2007.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

It's all connected: The power of proportional reasoning to understand mathematics concepts : grades K-8. Sausalito, CA: Math Solutions Publications, 2011.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Kuhrasch, Cindy. Connect!! An Integrated Health and PE Curriculum for Grades K-4. Moving Ahead, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Mierzwik, Diane. Quick and Easy Ways to Connect with Students and Their Parents, Grades K-8: Improving Student Achievement Through Parent Involvement. Skyhorse Publishing Company, Incorporated, 2016.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Mierzwik, Nancy Diane. Quick and Easy Ways to Connect With Students and Their Parents, Grades K-8: Improving Student Achievement Through Parent Involvement. Corwin Press, 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Mierzwik, Nancy Diane. Quick and Easy Ways to Connect With Students and Their Parents, Grades K-8: Improving Student Achievement Through Parent Involvement. Corwin Press, 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Quick and Easy Ways to Connect with Students and Their Parents, Grades K-8: Improving Student Achievement Through Parent Involvement. Skyhorse Publishing Company, Incorporated, 2016.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "K - connected graphs"

1

Gupta, Arvind, Naomi Nishimura, Andrzej Proskurowski, and Prabhakar Ragde. "Embeddings of k-Connected Graphs of Pathwidth k." In Algorithm Theory - SWAT 2000, 111–24. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-44985-x_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Jung, Heinz Adolf. "Degree Bounds for Long Paths and Cycles in k-Connected Graphs." In Computational Discrete Mathematics, 56–60. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-45506-x_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Barbato, Michele, Roland Grappe, Mathieu Lacroix, and Emiliano Lancini. "On k-edge-connected Polyhedra: Box-TDIness in Series-Parallel Graphs." In Lecture Notes in Computer Science, 27–41. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-53262-8_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Wada, Koichi, and Wei Chen. "Optimal Fault-Tolerant Routings for k-Connected Graphs with Smaller Routing Tables." In Graph-Theoretic Concepts in Computer Science, 302–13. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-40064-8_28.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Chu, Yan, Jianxi Fan, Wenjun Liu, and Cheng-Kuan Lin. "PTAS for Minimum k-Path Connected Vertex Cover in Growth-Bounded Graphs." In Algorithms and Architectures for Parallel Processing, 114–26. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-11197-1_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Manthey, Bodo, and Marten Waanders. "Approximation Algorithms for k-Connected Graph Factors." In Approximation and Online Algorithms, 1–12. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-28684-6_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Ishii, Toshimasa, and Hiroshi Nagamochi. "On the Minimum Augmentation of an ℓ-Connected Graph to a k-Connected Graph." In Algorithm Theory - SWAT 2000, 286–99. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-44985-x_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Hasunuma, Toru. "Augmenting a Tree to a k-Arbor-Connected Graph with Pagenumber k." In Lecture Notes in Computer Science, 356–69. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-79987-8_25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Taoka, Satoshi, and Toshimasa Watanabe. "Minimum augmentation to k-edge-connect specified vertices of a graph." In Algorithms and Computation, 217–25. Berlin, Heidelberg: Springer Berlin Heidelberg, 1994. http://dx.doi.org/10.1007/3-540-58325-4_184.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Zhang, Zhao, Xiaohui Huang, and Lina Chen. "A Simpler Method to Obtain a PTAS for Connected k-Path Vertex Cover in Unit Disk Graph." In Wireless Algorithms, Systems, and Applications, 584–92. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-60033-8_50.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "K - connected graphs"

1

Wen, Dong, Lu Qin, Ying Zhang, Lijun Chang, and Ling Chen. "Enumerating k-Vertex Connected Components in Large Graphs." In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 2019. http://dx.doi.org/10.1109/icde.2019.00014.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Sim, K. A., T. S. Tan, and K. B. Wong. "On the shortest path in some k-connected graphs." In ADVANCES IN INDUSTRIAL AND APPLIED MATHEMATICS: Proceedings of 23rd Malaysian National Symposium of Mathematical Sciences (SKSM23). Author(s), 2016. http://dx.doi.org/10.1063/1.4954598.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Burathep, Kunanon, Jittat Fakcharoenphol, and Nonthaphat Wongwattanakij. "Approximating k-Connected m-Dominating Sets in Disk Graphs." In 2020 24th International Computer Science and Engineering Conference (ICSEC). IEEE, 2020. http://dx.doi.org/10.1109/icsec51790.2020.9375178.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Kortsarz, G., and Z. Nutov. "Approximation algorithm for k-node connected subgraphs via critical graphs." In the thirty-sixth annual ACM symposium. New York, New York, USA: ACM Press, 2004. http://dx.doi.org/10.1145/1007352.1007381.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Xing, Kai, Wei Cheng, E. K. Park, and Shmuel Rotenstreich. "Distributed Connected Dominating Set Construction in Geometric k-Disk Graphs." In 2008 28th IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE, 2008. http://dx.doi.org/10.1109/icdcs.2008.39.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Hamid, Brahim, Quentin Rouland, and Jason Jaskolka. "Distributed Maintenance of a Spanning Tree of k-Connected Graphs." In 2019 IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC). IEEE, 2019. http://dx.doi.org/10.1109/prdc47002.2019.00052.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Cheriyan, Joseph, and Laszlo A. Vegh. "Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs." In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2013. http://dx.doi.org/10.1109/focs.2013.12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Fernandes, Cristina G., Carla N. Lintzmayer, and Mário César San Felice. "Leafy spanning k-forests." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16375.

Full text
Abstract:
We denote by Maximum Leaf Spanning k-Forest the problem of, given a positive integer k and a graph G with at most k components, finding a spanning forest in G with at most k components and the maximum number of leaves. A leaf in a forest is defined as a vertex of degree at most one. The case k = 1 for connected graphs is known to be NP-hard, and is well studied in the literature, with the best approximation algorithm proposed more than 20 years ago by Solis-Oba. The best known approximation algorithm for Maximum Leaf Spanning k-Forest with a slightly different leaf definition is a 3-approximation based on an approach by Lu and Ravi for the k = 1 case. We extend the algorithm of Solis-Oba to achieve a 2-approximation for Maximum Leaf Spanning k-Forest.
APA, Harvard, Vancouver, ISO, and other styles
9

Omai, M. M., C. N. Campos, and A. G. Luiz. "The (2,1)-total number of near-ladder graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16390.

Full text
Abstract:
A $(2,1)$-total labelling of a simple graph $G$ is a function $\pi \colon V(G)\cup E(G) \to \{0, \ldots, k\}$ such that: $\pi(u) \neq \pi(v)$ for $uv \in E(G)$; $\pi(uv) \neq \pi(vw)$ for $uv, vw \in E(G)$; and $|\pi(uv)-\pi(u)| \geq 2$ and $|\pi(uv)-\pi(v)| \geq 2$ for $uv \in E(G)$. The $(2,1)$-total number $\lambda_2^t(G)$ of $G$ is the least $k$ for which $G$ admits such a labelling. In 2008, Havet and Yu conjectured that $\lambda_2^t(G)\leq 5$ for every connected graph $G \not\cong K_4$ with $\Delta(G) \leq 3$. We prove that, for near-ladder graphs, $\lambda_2^t(G)=5$, verifying Havet and Yu's Conjecture for this class.
APA, Harvard, Vancouver, ISO, and other styles
10

Chen, Yankai, Jie Zhang, Yixiang Fang, Xin Cao, and Irwin King. "Efficient Community Search over Large Directed Graph: An Augmented Index-based Approach." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/490.

Full text
Abstract:
Given a graph G and a query vertex q, the topic of community search (CS), aiming to retrieve a dense subgraph of G containing q, has gained much attention. Most existing works focus on undirected graphs which overlooks the rich information carried by the edge directions. Recently, the problem of community search over directed graphs (or CSD problem) has been studied [Fang et al., 2019b]; it finds a connected subgraph containing q, where the in-degree and out-degree of each vertex within the subgraph are at least k and l, respectively. However, existing solutions are inefficient, especially on large graphs. To tackle this issue, in this paper we propose a novel index called D-Forest, which allows a CSD query to be completed within the optimal time cost. We further propose efficient index construction methods. Extensive experiments on six real large graphs show that our index-based query algorithm is up to two orders of magnitude faster than existing solutions.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'K - connected graphs' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography