Добірка наукової літератури з теми "Contraction perfect graphs"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Contraction perfect graphs".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Contraction perfect graphs"
Diner, Öznur Yaşar, Daniël Paulusma, Christophe Picouleau, and Bernard Ries. "Contraction and deletion blockers for perfect graphs and H-free graphs." Theoretical Computer Science 746 (October 2018): 49–72. http://dx.doi.org/10.1016/j.tcs.2018.06.023.
Повний текст джерелаBertschi, Marc E. "Perfectly contractile graphs." Journal of Combinatorial Theory, Series B 50, no. 2 (December 1990): 222–30. http://dx.doi.org/10.1016/0095-8956(90)90077-d.
Повний текст джерелаMaffray, Frédéric, and Nicolas Trotignon. "Algorithms for Perfectly Contractile Graphs." SIAM Journal on Discrete Mathematics 19, no. 3 (January 2005): 553–74. http://dx.doi.org/10.1137/s0895480104442522.
Повний текст джерелаSales, Cláudia Linhares, Frédéric Maffray, and Bruce Reed. "On Planar Perfectly Contractile Graphs." Graphs and Combinatorics 13, no. 2 (June 1997): 167–87. http://dx.doi.org/10.1007/bf03352994.
Повний текст джерелаRusu, Irena. "Perfectly contractile diamond-free graphs." Journal of Graph Theory 32, no. 4 (December 1999): 359–89. http://dx.doi.org/10.1002/(sici)1097-0118(199912)32:4<359::aid-jgt5>3.0.co;2-u.
Повний текст джерелаSales, Cláudia Linhares, and Frédéric Maffray. "On dart-free perfectly contractile graphs." Theoretical Computer Science 321, no. 2-3 (August 2004): 171–94. http://dx.doi.org/10.1016/j.tcs.2003.11.026.
Повний текст джерелаLévêque, Benjamin, and Frédéric Maffray. "Coloring Bull-Free Perfectly Contractile Graphs." SIAM Journal on Discrete Mathematics 21, no. 4 (January 2008): 999–1018. http://dx.doi.org/10.1137/06065948x.
Повний текст джерелаMaffray, Frédéric, and Nicolas Trotignon. "A class of perfectly contractile graphs." Journal of Combinatorial Theory, Series B 96, no. 1 (January 2006): 1–19. http://dx.doi.org/10.1016/j.jctb.2005.06.011.
Повний текст джерелаPANDA, SWARUP. "Inverses of bicyclic graphs." Electronic Journal of Linear Algebra 32 (February 6, 2017): 217–31. http://dx.doi.org/10.13001/1081-3810.3322.
Повний текст джерелаFischer, Ilse, and C. H. C. Little. "Even Circuits of Prescribed Clockwise Parity." Electronic Journal of Combinatorics 10, no. 1 (November 24, 2003). http://dx.doi.org/10.37236/1738.
Повний текст джерелаДисертації з теми "Contraction perfect graphs"
Dupont, Bouillard Alexandre. "Co-k-plexes and k-defective coloring : polytopes and algorithms." Electronic Thesis or Diss., Paris 13, 2024. http://www.theses.fr/2024PA131019.
Повний текст джерелаThis thesis proposes several results about co-k-plexes, which are vertex sets inducing a graph with maximum degree k-1 and the k-defective coloring which consists in covering the vertices of a graph with a minimum number of co-k-plexes. The thesis is split into two parts, each starting with a dedicated state-of-the-art chapter.The first part investigates several characterizations of a new subclass of perfect graphs that we call contraction-perfect graphs, which is the set of perfect graphs remaining perfect after the contraction of any edge set.Contractions in perfect graphs: We characterize this graph class in four different manners.We give a characterization of contraction-perfect graphs in terms of forbidden induced subgraphs, and a polynomial algorithm to recognize them. On such graphs, solving the maximum weighted co-2-plex problem is doable in polynomial time. This is done by considering what we call the utter graph u(G) of a graph G, whose stable sets are in bijection with the co-2-plexes of G. We show that u(G) is perfect if and only if G is contraction-perfect and as the maximum stable set problem is solvable in polynomial time on perfect graphs we obtain the polynomiality result of the maximum weighted co-2-plex problem on contraction-perfect graphs.The maximum weighted co-2-plex problem : We investigate an extended formulation for the co-2-plex polytope of contraction-perfect graphs obtained by considering the stable set polytope of its utter graph. Note that this formulation becomes compact for chordal graphs. Moreover, with additional integrity constraints, this formulation becomes a valid ILP formulation for any graph G, leading to a comparison between this extended ILP formulation with a formulation of the literature. From an experimental point of view, we propose different implementation variants of our formulation and conclude that they are competitive with the one from the literature. The second part of the thesis is about column generation: we describe a method from the literature solving the k-defective coloring proposed by Furini et al. We then implement this method within the SCIP framework to let us add new techniques.The graph coloring problem and alternation strategies: Column generation is known to suffer from the tailing off effect that consists of a sequence of non-improving subsets of variables. To tackle this issue, we tried to alternate between cutting and pricing and in particular proposed two parameterized strategies hoping that cutting earlier would help to get rid of the tailing-off effect. The second improvement of this framework has been proposed in the literature under the name of {dual optimal inequalities}: this technique consists in adding to the RMP a set of columns that are inequalities cutting no optimal points of the dual RMP. This method has been experimentally successful in stabilizing the column generation for the case k=1, we hence tried to combine primal/dual inequalities and alternation strategies in several manners. For the case k=2 we propose to use dedicated valid inequalities, called triangle constraints. We also propose a set of dual inequalities for any k and showed that it implied significant improvements. We then applied a technique similar to our work on the case k=1 combining primal and dual inequalities, for the case k=2. Note that the dual inequalities we propose are of a new type that has not been investigated in the literature: they may cut every dual optimal point but, when considered as variables of the primal, they never add integer solutions that cannot be mapped into an integer solution of the original problem with the same optimum value. Finally, we recap the results of the thesis and give perspectives for each of the chapters
Частини книг з теми "Contraction perfect graphs"
Linhares Sales, Cláudia, and Frédéric Maffray. "On Dart-Free Perfectly Contractile Graphs Extended Abstract." In Lecture Notes in Computer Science, 135–44. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/10719839_15.
Повний текст джерела