Bibliographies thématiques / Partitioning into vertex-disjoint cycles

Littérature scientifique sur le sujet « Partitioning into vertex-disjoint cycles »

Auteur : Grafiati

Publié le 4 mai 2024

Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres

Choisissez une source :

Consultez les listes thématiques d’articles de revues, de livres, de thèses, de rapports de conférences et d’autres sources académiques sur le sujet « Partitioning into vertex-disjoint cycles ».

À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.

Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.

Articles de revues sur le sujet "Partitioning into vertex-disjoint cycles"

ŁUCZAK, TOMASZ, VOJTĚCH RÖDL et ENDRE SZEMERÉDI. « Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles ». Combinatorics, Probability and Computing 7, n^o 4 (décembre 1998) : 423–36. http://dx.doi.org/10.1017/s0963548398003599.

Texte intégral

Résumé :

We prove that there exists n0, such that, for every n[ges ]n0 and every 2-colouring of the edges of the complete graph Kn, one can find two vertex-disjoint monochromatic cycles of different colours which cover all vertices of Kn.

Styles APA, Harvard, Vancouver, ISO, etc.

Lin, Mugang, Jianxin Wang, Qilong Feng et Bin Fu. « Randomized Parameterized Algorithms for the Kidney Exchange Problem ». Algorithms 12, n^o 2 (25 février 2019) : 50. http://dx.doi.org/10.3390/a12020050.

Texte intégral

Résumé :

In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically 2 ≤ L ≤ 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases L = 3 and L ≥ 3 , and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.

Styles APA, Harvard, Vancouver, ISO, etc.

Korostil, Alexander V., et Andrei V. Nikolaev. « Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph ». Modeling and Analysis of Information Systems 28, n^o 1 (24 mars 2021) : 6–21. http://dx.doi.org/10.18255/1818-1015-2021-1-6-21.

Texte intégral

Résumé :

We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skeleton of the symmetric and asymmetric traveling salesperson polytopes is an NP-complete problem. On the other hand, a suffcient condition for two vertices to be non-adjacent can be formulated as a combinatorial problem of finding a Hamiltonian decomposition of a 4-regular multigraph. We present two backtracking algorithms for verifying vertex non-adjacency in the 1-skeleton of the traveling salesperson polytope and constructing a Hamiltonian decomposition: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. Based on the results of the computational experiments for undirected multigraphs, both backtracking algorithms lost to the known heuristic general variable neighborhood search algorithm. However, for directed multigraphs, the algorithm based on chain fixing of edges showed comparable results with heuristics on instances with existing solutions, and better results on instances of the problem where the Hamiltonian decomposition does not exist.

Styles APA, Harvard, Vancouver, ISO, etc.

RAJASINGH, INDRA, M. AROCKIARAJ, BHARATI RAJAN et PAUL MANUEL. « CIRCULAR WIRELENGTH OF GENERALIZED PETERSEN GRAPHS ». Journal of Interconnection Networks 12, n^o 04 (décembre 2011) : 319–35. http://dx.doi.org/10.1142/s0219265911003027.

Texte intégral

Résumé :

In this paper we formulate the Vertex Congestion Lemma leading to a new technique in computing the exact wirelength of an embedding. We compute the circular wirelength of generalized Petersen graphs by partitioning the vertices as well as the edges of cycles. Further we obtain the linear wirelength of circular ladders. Our algorithms produce optimal values in linear time.

Styles APA, Harvard, Vancouver, ISO, etc.

Nöllenburg, Martin, Roman Prutkin et Ignaz Rutter. « Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions ». International Journal of Computational Geometry & ; Applications 27, n^o 01n02 (mars 2017) : 121–58. http://dx.doi.org/10.1142/s0218195917600068.

Texte intégral

Résumé :

A greedily routable region (GRR) is a closed subset of [Formula: see text], in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected.

Styles APA, Harvard, Vancouver, ISO, etc.

BODLAENDER, HANS L. « ON DISJOINT CYCLES ». International Journal of Foundations of Computer Science 05, n^o 01 (mars 1994) : 59–68. http://dx.doi.org/10.1142/s0129054194000049.

Texte intégral

Résumé :

It is shown, that for each constant k≥1, the following problems can be solved in [Formula: see text] time: given a graph G, determine whether G has k vertex disjoint cycles, determine whether G has k edge disjoint cycles, determine whether G has a feedback vertex set of size ≤k. Also, every class [Formula: see text], that is closed under minor taking, taking, and that does not contain the graph consisting of k disjoint copies of K3, has an [Formula: see text] membership test algorithm.

Styles APA, Harvard, Vancouver, ISO, etc.

Li, Jianping, et George Steiner. « Partitioning a graph into vertex-disjoint paths ». Studia Scientiarum Mathematicarum Hungarica 42, n^o 3 (1 septembre 2005) : 277–94. http://dx.doi.org/10.1556/sscmath.42.2005.3.3.

Texte intégral

Résumé :

Let G=(V,E) be a simple graph of order n. We consider the problem of partitioning G into vertex-disjoint paths. We obtain the following new results: (i) For any positive integer k, if dG(x)+dG(y) = n-k-1 for every pair x, y of nonadjacent vertices in G, then G can be partitioned into k vertex-disjoint paths, unless G belongs to certain classes of extremal graphs which we characterize; (ii) For the case k=2, we strengthen our result by showing that for any two positive integers p1 and p2 satisfying n= p1+ p2,if dG(x)+dG(y) = n-3 for every pair x, y of nonadjacent vertices in G and G does not belong to classes of exceptional graphs we define, then G can be partitioned into two vertex-disjoint paths P1 and P2 of order p1 and p2, respectively. These results are generalizations of some classical results of Dirac and Ore, and also lead to new sufficient conditions for the existence of a Hamilton path in a graph.

Styles APA, Harvard, Vancouver, ISO, etc.

VERSTRAËTE, JACQUES. « A Note on Vertex-Disjoint Cycles ». Combinatorics, Probability and Computing 11, n^o 1 (janvier 2002) : 97–102. http://dx.doi.org/10.1017/s0963548301004904.

Texte intégral

Résumé :

Häggkvist and Scott asked whether one can find a quadratic function q(k) such that, if G is a graph of minimum degree at least q(k), then G contains vertex-disjoint cycles of k consecutive even lengths. In this paper, it is shown that if G is a graph of average degree at least k2+19k+10 with sufficiently many vertices, then G contains vertex-disjoint cycles of k consecutive even lengths, answering the above question in the affirmative. The coefficient of k2 cannot be decreased and, in this sense, this result is best possible.

Styles APA, Harvard, Vancouver, ISO, etc.

Egawa, Yoshimi, Ralph J. Faudree, Ervin Györi, Yoshiyasu Ishigami, Richard H. Schelp et Hong Wang. « Vertex-Disjoint Cycles Containing Specified Edges ». Graphs and Combinatorics 16, n^o 1 (1 mars 2000) : 81–92. http://dx.doi.org/10.1007/s003730050005.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Li, Ruijuan, Juanjuan Liang, Xinhong Zhang et Yubao Guo. « Vertex-disjoint cycles in local tournaments ». Discrete Mathematics 343, n^o 12 (décembre 2020) : 112127. http://dx.doi.org/10.1016/j.disc.2020.112127.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Plus de sources

Thèses sur le sujet "Partitioning into vertex-disjoint cycles"

Kobeissi, Mohamed. « Plongement de graphes dans l'hypercube ». Phd thesis, Grenoble 1, 2001. https://theses.hal.science/tel-00004683.

Texte intégral

Résumé :

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

Styles APA, Harvard, Vancouver, ISO, etc.

Bai, Yandong. « Arc colorings and cycles in digraphs ». Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112356/document.

Texte intégral

Résumé :

Cette thèse étudie la coloration d'arcs et de cycles dans les graphes orientés. Elle se concentre sur les sujets suivants : la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés, les cycles courts dans les graphes orientés avec des sous-graphes interdits, les cycles sommet-disjoints dans dans les tournois bipartis, les cycle-facteurs dans les tournois bipartis régulier et les arcs universels dans les tournois. La thèse est basée sur cinq articles originaux publiés ou présentés dans des journaux. Les principaux résultats sont les suivants. Nous introduisons la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés. Nous avons proposé une conjecture sur le nombre arc-chromatique sommet-distingué et nous avons aussi donné quelque résultats partiels. Nous avons étendu un résultat de Razborov en prouvant que la conjecture de Caccetta-Häggkvist est vraie pour certains graphes orientés avec des sous-graphes interdits. Nous avons montré que chaque tournoi biparti avec degré sortant minimum au moins qr-1 contient r cycles de sommets-disjoints de toutes longueurs possibles. Le cas spécial q=2 confirme le cas du tournoi biparti de la conjecture de Bermond-Thomassen. Nous avons montré que chaque tournoi biparti k-régulier avec k>2 que l'on notera B a deux cycles complémentaires de longueurs 6 et |V(B)-6|, à moins que B soit isomorphe à un graphe spécifique, étayant ainsi une conjecture sur des 2-cycles-facteurs dans les tournois bipartis. En outre, nous montrons que tous les tournois bipartis réguliers ont un k-cycle-facteur. Nous donnons une condition nécessaire et suffisante pour l'existence d'un arc universel dans un tournoi et nous caractérisons tous les tournois où chaque arc est universel
In this thesis, we study arc colorings and cycles in digraphs. The following topics are considered: vertex-distinguishing proper arc colorings in digraphs, short cycles in digraphs with forbidden subgraphs , disjoint cycles in bipartite tournaments, cycle factors in regualr bipartite tournaments and universal arcs in tournaments. The main results are contained in five original articles published or submitted to an international journal. We introduce vertex-distinguishing proper arc colorings of digraphs. A conjecture on the vertex-distinguishing arc-chromatic number is given and some partial results are obtained. We extend a result of Razborov by proving that the Caccetta-Häggkvist conjecture is true for digraphs with certain induced forbidden subgraphs or with certain forbidden subgraphs. We show that every bipartite tournament with minimum outdegree at least qr-1 has r vertex disjoint cycles of any given possible lengths. The special case q=2 of the result verifies the bipartite tournament case of the Bermond-Thomassen conjecture. As a partial support of a conjecture on 2-cycle-factors in bipartite tournaments, we prove that every k-regular bipartite tournament B with k>2 has two complementary cycles of lengths 6 and |V(B)|-6, unless B is isomorphic to a special digraph. Besides, we show that every k-connected regular bipartite tournament has a k-cycle-factor. We also give a sufficient and necessary condition for the existence of a universal arc in a tournament and characterize all the tournaments in which every arc is universal

Styles APA, Harvard, Vancouver, ISO, etc.

Chapitres de livres sur le sujet "Partitioning into vertex-disjoint cycles"

Kloks, Ton, C. M. Lee et Jiping Liu. « New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs ». Dans Graph-Theoretic Concepts in Computer Science, 282–95. Berlin, Heidelberg : Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-36379-3_25.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Actes de conférences sur le sujet "Partitioning into vertex-disjoint cycles"

Xiao, Mingyu, et Xuanbei Wang. « Exact Algorithms and Complexity of Kidney Exchange ». Dans Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California : International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/77.

Texte intégral

Résumé :

Kidney Exchange is an approach to donor kidney transplantation where patients with incompatible donors swap kidneys to receive a compatible kidney. Since it was first put forward in 1986, increasing amount of people have gotten a life-saving kidney with the popularity of Kidney Exchange, as patients have more opportunities to get saved in this way. This growth is making the problem of optimally matching patients to donors more difficult to solve. The central problem, indeed, is the NP-hard problem to find the largest vertex-disjoint packing of cycles and chains in a graph that represents the compatibility between patients and donors, where due to the human resource limitation we may have constraints on the maximum length of cycles and chains. This paper mainly contributes to algorithms from theory for this problem with and without length constraints (restricted and free versions). We give: 1. A single-exponential exact algorithm based on subset convolution for the two versions; 2. An FPT algorithm for the free version with parameter being the number of vertex ``types'' in the graph.

Styles APA, Harvard, Vancouver, ISO, etc.

Ceylan, Esra, Jiehua Chen et Sanjukta Roy. « Optimal Seat Arrangement : What Are the Hard and Easy Cases ? » Dans Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California : International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/285.

Texte intégral

Résumé :

We study four NP-hard optimal seat arrangement problems which each have as input a set of n agents, where each agent has cardinal preferences over other agents, and an n-vertex undirected graph (called the seat graph). The task is to assign each agent to a distinct vertex in the seat graph such that either the sum of utilities or the minimum utility is maximized, or it is envy-free or exchange-stable. Aiming at identifying hard and easy cases, we extensively study the algorithmic complexity of the four problems by looking into natural graph classes for the seat graph (e.g., paths, cycles, stars, or matchings), problem-specific parameters (e.g., the number of non-isolated vertices in the seat graph or the maximum number of agents towards whom an agent has non-zero preferences), and preference structures (e.g., non-negative or symmetric preferences). For strict preferences and seat graphs with disjoint edges and isolated vertices, we correct an error in the literature and show that finding an envy-free arrangement remains NP-hard in this case.

Styles APA, Harvard, Vancouver, ISO, etc.

Maiti, Arnab, et Palash Dey. « Parameterized Algorithms for Kidney Exchange ». Dans Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California : International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/58.

Texte intégral

Résumé :

In kidney exchange programs, multiple patient-donor pairs each of whom are otherwise incompatible, exchange their donors to receive compatible kidneys. The Kidney Exchange problem is typically modelled as a directed graph where every vertex is either an altruistic donor or a pair of patient and donor; directed edges are added from a donor to its compatible patients. The computational task is to find if there exists a collection of disjoint cycles and paths starting from altruistic donor vertices of length at most l_c and l_p respectively that covers at least some specific number t of non-altruistic vertices (patients). We study parameterized algorithms for the kidney exchange problem in this paper. Specifically, we design FPT algorithms parameterized by each of the following parameters: (1) the number of patients who receive kidney, (2) treewidth of the input graph + max{l_p, l_c}, and (3) the number of vertex types in the input graph when l_p <= l_c. We also present interesting algorithmic and hardness results on the kernelization complexity of the problem. Finally, we present an approximation algorithm for an important special case of Kidney Exchange.

Styles APA, Harvard, Vancouver, ISO, etc.

Nous offrons des réductions sur tous les plans premium pour les auteurs dont les œuvres sont incluses dans des sélections littéraires thématiques. Contactez-nous pour obtenir un code promo unique!