Found 55 Documents (Results 1–55)
On a countable family of boundary graph classes for the dominating set problem. (Russian. English summary) Zbl 1521.05168
Tree-width dichotomy. (English) Zbl 1487.05221
Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time. (English) Zbl 1517.05164
Clique-width: harnessing the power of atoms. (English) Zbl 07636200
Adler, Isolde (ed.) et al., Graph-theoretic concepts in computer science. 46th international workshop, WG 2020, Leeds, UK, June 24–26, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12301, 119-133 (2020).
MSC:
68R10
Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width. (English) Zbl 1435.68112
A boundary class for the \(k\)-path partition problem. (English) Zbl 1453.68138
Bagdasar, Ovidiu (ed.) et al., TREPAM 2017. Proceedings of the 1st international conference on recent trends in pure and applied mathematics, Alba-Iulia, Romania, July 31 – August 4, 2017. Amsterdam: Elsevier. Electron. Notes Discrete Math. 67, 49-56 (2018).
Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time. (English) Zbl 1380.05147
Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time. (English) Zbl 1377.05185
On König graphs with respect to \(P_4\). (Russian, English) Zbl 1399.05134
Diskretn. Anal. Issled. Oper. 24, No. 3, 61-79 (2017); translation in J. Appl. Ind. Math. 11, No. 3, 421-430 (2017).
Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs. (Russian, English) Zbl 1399.05174
Diskretn. Anal. Issled. Oper. 24, No. 3, 35-60 (2017); translation in J. Appl. Ind. Math. 11, No. 3, 400-414 (2017).
Critical elements in combinatorially closed families of graph classes. (Russian, English) Zbl 1374.05186
Diskretn. Anal. Issled. Oper. 24, No. 1, 81-96 (2017); translation in J. Appl. Ind. Math. 11, No. 1, 99-106 (2017).
A sufficient condition to extend polynomial results for the maximum independent set problem. (English) Zbl 1350.05123
Critical hereditary graph classes: a survey. (English) Zbl 1364.90333
MSC:
90C35
A new graph construction of unbounded clique-width. (English) Zbl 1355.05188
Korpelainen, Nicholas (ed.), TCDM 2016. Proceedings of the 1st IMA conference on theoretical and computational discrete mathematics, University of Derby, Derby, UK, March 22–23, 2016. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 56, 31-36 (2016).
A complexity dichotomy and a new boundary class for the dominating set problem. (English) Zbl 1354.90111
A boundary property for upper domination. (English) Zbl 1392.68195
Mäkinen, Veli (ed.) et al., Combinatorial algorithms. 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17–19, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-44542-7/pbk; 978-3-319-44543-4/ebook). Lecture Notes in Computer Science 9843, 229-240 (2016).
The width and integer optimization on simplices with bounded minors of the constraint matrices. (English) Zbl 1377.90059
MSC:
90C10
A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs. (English) Zbl 1332.05108
Contraction blockers for graphs with forbidden induced paths. (English) Zbl 1459.68156
Paschos, Vangelis Th. (ed.) et al., Algorithms and complexity. 9th international conference, CIAC 2015, Paris, France, May 20–22, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9079, 194-207 (2015).
The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs. (English) Zbl 1315.05061
Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. (English) Zbl 1236.05127
On the complexity of the dominating induced matching problem in hereditary classes of graphs. (English) Zbl 1213.05206
Max-Cut and containment relations in graphs. (English) Zbl 1309.05173
Thilikos, Dimitrios M. (ed.), Graph theoretic concepts in computer science. 36th international workshop, WG 2010, Zarós, Crete, Greece, June 28–30, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-16925-0/pbk). Lecture Notes in Computer Science 6410, 15-26 (2010).
On the number of boundary classes in the 3-colouring problem. (English. Russian original) Zbl 1237.05083
Discrete Math. Appl. 19, No. 6, 625-630 (2009); translation from Diskretn. Mat. 21, No. 4, 129-134 (2009).
Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles. (English) Zbl 1170.68019
Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs. (English) Zbl 1141.05068
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem. (English) Zbl 1143.68059
New applications of clique separator decomposition for the maximum weight stable set problem. (English) Zbl 1118.68101
Filter Results by …
Document Type
- Journal Articles (49)
- Collection Articles (6)
all
top 5
Author
- Lozin, Vadim Vladislavovich (17)
- Malyshev, Dmitriĭ Sergeevich (13)
- Mosca, Raffaele (9)
- Brandstädt, Andreas (6)
- Korpelainen, Nicholas (5)
- Ries, Bernard (4)
- Novotná, Jana (3)
- Paulusma, Daniël (3)
- Rzążewski, Paweł (3)
- Zamaraev, Victor A. (3)
- AbouEisha, Hassan (2)
- Alekseev, Vladimir E. (2)
- Dabrowski, Konrad Kazimierz (2)
- Hussain, Shahid (2)
- Kamiński, Marcin (2)
- Korobitsyn, Dmitry V. (2)
- Masařík, Tomáš (2)
- Monnot, Jérôme (2)
- Munaro, Andrea (2)
- Razgon, Igor (2)
- Alecu, Bogdan (1)
- Boliac, Rodica (1)
- Cardoso, Domingos Moreira (1)
- Chirkov, Aleksandr Yu. (1)
- Dakhno, G. S. (1)
- Dallard, Clément (1)
- Diner, Öznur Yaşar (1)
- Galby, Esther (1)
- Ganian, Robert (1)
- Gerber, Michael U. (1)
- Giakoumakis, Vassilis (1)
- Gribanov, Dmitriĭ Vladimirovich (1)
- Hatzel, Meike (1)
- Hertz, Alain (1)
- Hoàng, Chính T. (1)
- Krnc, Matjaž (1)
- Lê Văn Băng (1)
- Maffray, Frédéric (1)
- Mahfud, Suhail (1)
- Milanič, Martin (1)
- Mokeev, Dmitriĭ Borisovich (1)
- Okrasa, Karolina (1)
- Pardalos, Panos M. (1)
- Picouleau, Christophe (1)
- Pilipczuk, Michał (1)
- Purcell, Christopher J. (1)
- Raman, Venkatesh (1)
- Rautenbach, Dieter (1)
- Rombach, Puck (1)
- Saurabh, Saket (1)
- Sirotkin, Dmitrii V. (1)
- Tiskin, Alexandre (1)
- Van Leeuwen, Erik Jan (1)
- Walczak, Bartosz (1)
all
top 5
Serial
- Discrete Appl. Math. (10)
- Theor. Comput. Sci. (10)
- Discrete Math. (4)
- J. Graph Theory (4)
- Diskretn. Anal. Issled. Oper. (4)
- Algorithmica (3)
- Optim. Lett. (3)
- Graphs Comb. (2)
- J. Comb. Optim. (2)
- Inf. Process. Lett. (1)
- J. Comb. Theory, Ser. B (1)
- Eur. J. Comb. (1)
- Order (1)
- Discrete Math. Appl. (1)
- Eur. J. Oper. Res. (1)
- Comb. Probab. Comput. (1)
