Relevant bibliographies by topics / Partitioning into vertex-disjoint cycles

Contents

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

Academic literature on the topic 'Partitioning into vertex-disjoint cycles'

Author: Grafiati
Published: 4 May 2024

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 'Partitioning into vertex-disjoint cycles.'

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 "Partitioning into vertex-disjoint cycles"

1

ŁUCZAK, TOMASZ, VOJTĚCH RÖDL, and ENDRE SZEMERÉDI. "Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles." Combinatorics, Probability and Computing 7, no. 4 (December 1998): 423–36. http://dx.doi.org/10.1017/s0963548398003599.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
2

Lin, Mugang, Jianxin Wang, Qilong Feng, and Bin Fu. "Randomized Parameterized Algorithms for the Kidney Exchange Problem." Algorithms 12, no. 2 (February 25, 2019): 50. http://dx.doi.org/10.3390/a12020050.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

RAJASINGH, INDRA, M. AROCKIARAJ, BHARATI RAJAN, and PAUL MANUEL. "CIRCULAR WIRELENGTH OF GENERALIZED PETERSEN GRAPHS." Journal of Interconnection Networks 12, no. 04 (December 2011): 319–35. http://dx.doi.org/10.1142/s0219265911003027.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
5

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

BODLAENDER, HANS L. "ON DISJOINT CYCLES." International Journal of Foundations of Computer Science 05, no. 01 (March 1994): 59–68. http://dx.doi.org/10.1142/s0129054194000049.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
7

Li, Jianping, and George Steiner. "Partitioning a graph into vertex-disjoint paths." Studia Scientiarum Mathematicarum Hungarica 42, no. 3 (September 1, 2005): 277–94. http://dx.doi.org/10.1556/sscmath.42.2005.3.3.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
8

VERSTRAËTE, JACQUES. "A Note on Vertex-Disjoint Cycles." Combinatorics, Probability and Computing 11, no. 1 (January 2002): 97–102. http://dx.doi.org/10.1017/s0963548301004904.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
9

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

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

Li, Ruijuan, Juanjuan Liang, Xinhong Zhang, and Yubao Guo. "Vertex-disjoint cycles in local tournaments." Discrete Mathematics 343, no. 12 (December 2020): 112127. http://dx.doi.org/10.1016/j.disc.2020.112127.

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

Dissertations / Theses on the topic "Partitioning into vertex-disjoint cycles"

1

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

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Partitioning into vertex-disjoint cycles"

1

Kloks, Ton, C. M. Lee, and Jiping Liu. "New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs." In 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.

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

Conference papers on the topic "Partitioning into vertex-disjoint cycles"

1

Xiao, Mingyu, and Xuanbei Wang. "Exact Algorithms and Complexity of Kidney Exchange." In 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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
2

Ceylan, Esra, Jiehua Chen, and Sanjukta Roy. "Optimal Seat Arrangement: What Are the Hard and Easy Cases?" In 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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
3

Maiti, Arnab, and Palash Dey. "Parameterized Algorithms for Kidney Exchange." In 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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Partitioning into vertex-disjoint cycles' 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