Bonomo-Braberman, Flavia; Brito, Gastón Abel Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs. (English) Zbl 1528.05015 Discrete Appl. Math. 339, 53-77 (2023). MSC: 05C12 05C75 PDFBibTeX XMLCite \textit{F. Bonomo-Braberman} and \textit{G. A. Brito}, Discrete Appl. Math. 339, 53--77 (2023; Zbl 1528.05015) Full Text: DOI arXiv
Tsin, Yung H. A simple certifying algorithm for 3-edge-connectivity. (English) Zbl 1509.05169 Theor. Comput. Sci. 951, Article ID 113760, 26 p. (2023). MSC: 05C85 05C40 PDFBibTeX XMLCite \textit{Y. H. Tsin}, Theor. Comput. Sci. 951, Article ID 113760, 26 p. (2023; Zbl 1509.05169) Full Text: DOI arXiv
Soulignac, Francisco J. A certifying and dynamic algorithm for the recognition of proper circular-arc graphs. (English) Zbl 1517.05170 Theor. Comput. Sci. 889, 105-134 (2021). MSC: 05C85 05C62 PDFBibTeX XMLCite \textit{F. J. Soulignac}, Theor. Comput. Sci. 889, 105--134 (2021; Zbl 1517.05170) Full Text: DOI arXiv
Safe, Martín D. Circularly compatible ones, \(D\)-circularity, and proper circular-arc bigraphs. (English) Zbl 1462.05311 SIAM J. Discrete Math. 35, No. 2, 707-751 (2021). MSC: 05C75 05C62 05C85 05C20 PDFBibTeX XMLCite \textit{M. D. Safe}, SIAM J. Discrete Math. 35, No. 2, 707--751 (2021; Zbl 1462.05311) Full Text: DOI arXiv
Crespelle, Christophe Fully dynamic representations of interval graphs. (English) Zbl 1403.68158 Theor. Comput. Sci. 759, 14-49 (2019). MSC: 68R10 05C62 05C85 68Q25 PDFBibTeX XMLCite \textit{C. Crespelle}, Theor. Comput. Sci. 759, 14--49 (2019; Zbl 1403.68158) Full Text: DOI
Völlinger, Kim; Akili, Samira On a verification framework for certifying distributed algorithms: distributed checking and consistency. (English) Zbl 1508.68080 Baier, Christel (ed.) et al., Formal techniques for distributed objects, components, and systems. 38th IFIP WG 6.1 international conference, FORTE 2018, held as part of the 13th international federated conference on distributed computing techniques, DisCoTec 2018, Madrid, Spain, June 18–21, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10854, 161-180 (2018). MSC: 68N30 68W15 PDFBibTeX XMLCite \textit{K. Völlinger} and \textit{S. Akili}, Lect. Notes Comput. Sci. 10854, 161--180 (2018; Zbl 1508.68080) Full Text: DOI
Heggernes, Pinar; Issac, Davis; Lauri, Juho; Lima, Paloma T.; van Leeuwen, Erik Jan Rainbow vertex coloring bipartite graphs and chordal graphs. (English) Zbl 1512.05139 Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 83, 13 p. (2018). MSC: 05C15 05C85 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{P. Heggernes} et al., LIPIcs -- Leibniz Int. Proc. Inform. 117, Article 83, 13 p. (2018; Zbl 1512.05139) Full Text: DOI
Ke, Yuping; Cao, Yixin; Ouyang, Xiating; Li, Wenjun; Wang, Jianxin Unit interval vertex deletion: fewer vertices are relevant. (English) Zbl 1391.68058 J. Comput. Syst. Sci. 95, 109-121 (2018). MSC: 68Q25 05C62 05C85 PDFBibTeX XMLCite \textit{Y. Ke} et al., J. Comput. Syst. Sci. 95, 109--121 (2018; Zbl 1391.68058) Full Text: DOI arXiv
Francis, Mathew C.; Jacob, Dalu; Jana, Satyabrata Uniquely restricted matchings in interval graphs. (English) Zbl 1378.05137 SIAM J. Discrete Math. 32, No. 1, 148-172 (2018). MSC: 05C62 05C85 PDFBibTeX XMLCite \textit{M. C. Francis} et al., SIAM J. Discrete Math. 32, No. 1, 148--172 (2018; Zbl 1378.05137) Full Text: DOI arXiv
Laurent, M.; Seminaroti, M. A Lex-BFS-based recognition algorithm for Robinsonian matrices. (English) Zbl 1396.05051 Discrete Appl. Math. 222, 151-165 (2017). MSC: 05C30 05C65 05C85 PDFBibTeX XMLCite \textit{M. Laurent} and \textit{M. Seminaroti}, Discrete Appl. Math. 222, 151--165 (2017; Zbl 1396.05051) Full Text: DOI arXiv
Das, Ashok Kumar; Chakraborty, Ritapa Graphs and digraphs represented by intervals and circular arcs. (English) Zbl 1365.05107 Discrete Appl. Math. 228, 41-49 (2017). MSC: 05C20 PDFBibTeX XMLCite \textit{A. K. Das} and \textit{R. Chakraborty}, Discrete Appl. Math. 228, 41--49 (2017; Zbl 1365.05107) Full Text: DOI
Soulignac, Francisco J. Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory. (English) Zbl 1361.05089 J. Graph Algorithms Appl. 21, No. 4, 455-489 (2017). MSC: 05C62 05C85 PDFBibTeX XMLCite \textit{F. J. Soulignac}, J. Graph Algorithms Appl. 21, No. 4, 455--489 (2017; Zbl 1361.05089) Full Text: DOI
Laurent, Monique; Seminaroti, Matteo A Lex-BFS-based recognition algorithm for Robinsonian matrices. (English) Zbl 1383.68067 Paschos, Vangelis Th. (ed.) et al., Algorithms and complexity. 9th international conference, CIAC 2015, Paris, France, May 20–22, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-18172-1/pbk; 978-3-319-18173-8/ebook). Lecture Notes in Computer Science 9079, 325-338 (2015). MSC: 68T10 62H20 68R10 68T20 PDFBibTeX XMLCite \textit{M. Laurent} and \textit{M. Seminaroti}, Lect. Notes Comput. Sci. 9079, 325--338 (2015; Zbl 1383.68067) Full Text: DOI arXiv
Soulignac, Francisco J. Fully dynamic recognition of proper circular-arc graphs. (English) Zbl 1323.05125 Algorithmica 71, No. 4, 904-968 (2015). Reviewer: Vladimír Lacko (Košice) MSC: 05C85 05C62 05C40 68Q25 PDFBibTeX XMLCite \textit{F. J. Soulignac}, Algorithmica 71, No. 4, 904--968 (2015; Zbl 1323.05125) Full Text: DOI arXiv Link
Brown, David E.; Flesch, Breeann M. A characterization of 2-tree proper interval 3-graphs. (English) Zbl 1295.05200 J. Discrete Math. 2014, Article ID 143809, 7 p. (2014). MSC: 05C76 05C15 PDFBibTeX XMLCite \textit{D. E. Brown} and \textit{B. M. Flesch}, J. Discrete Math. 2014, Article ID 143809, 7 p. (2014; Zbl 1295.05200) Full Text: DOI
Kiyomi, Masashi; Saitoh, Toshiki; Uehara, Ryuhei Bipartite permutation graphs are reconstructible. (English) Zbl 1255.05122 Discrete Math. Algorithms Appl. 4, No. 3, 1250039, 14 p. (2012). MSC: 05C60 05C75 PDFBibTeX XMLCite \textit{M. Kiyomi} et al., Discrete Math. Algorithms Appl. 4, No. 3, 1250039, 14 p. (2012; Zbl 1255.05122) Full Text: DOI
Nikolopoulos, Stavros D.; Palios, Leonidas An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs. (English) Zbl 1251.05173 Theor. Comput. Sci. 452, 117-131 (2012). MSC: 05C99 68R10 PDFBibTeX XMLCite \textit{S. D. Nikolopoulos} and \textit{L. Palios}, Theor. Comput. Sci. 452, 117--131 (2012; Zbl 1251.05173) Full Text: DOI
McConnell, R. M.; Mehlhorn, K.; Näher, S.; Schweitzer, P. Certifying algorithms. (English) Zbl 1298.68289 Comput. Sci. Rev. 5, No. 2, 119-161 (2011). MSC: 68W01 68-02 PDFBibTeX XMLCite \textit{R. M. McConnell} et al., Comput. Sci. Rev. 5, No. 2, 119--161 (2011; Zbl 1298.68289) Full Text: DOI
Hung, Ruo-Wei; Chang, Maw-Shang An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs. (English) Zbl 1235.68083 Theor. Comput. Sci. 412, No. 39, 5351-5373 (2011). Reviewer: Jean-Luc Baril (Dijon) MSC: 68Q25 68R10 05C45 PDFBibTeX XMLCite \textit{R.-W. Hung} and \textit{M.-S. Chang}, Theor. Comput. Sci. 412, No. 39, 5351--5373 (2011; Zbl 1235.68083) Full Text: DOI
Lin, Min Chih; Rautenbach, Dieter; Soulignac, Francisco Juan; Szwarcfiter, Jayme Luiz Powers of cycles, powers of paths, and distance graphs. (English) Zbl 1213.05148 Discrete Appl. Math. 159, No. 7, 621-627 (2011). MSC: 05C38 05C12 PDFBibTeX XMLCite \textit{M. C. Lin} et al., Discrete Appl. Math. 159, No. 7, 621--627 (2011; Zbl 1213.05148) Full Text: DOI Link
Hung, Ruo-Wei; Chang, Maw-Shang Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs. (English) Zbl 1209.05244 Appl. Math. Lett. 24, No. 5, 648-652 (2011). MSC: 05C85 05C70 05C38 PDFBibTeX XMLCite \textit{R.-W. Hung} and \textit{M.-S. Chang}, Appl. Math. Lett. 24, No. 5, 648--652 (2011; Zbl 1209.05244) Full Text: DOI
Gutin, Gregory; Kim, Eun Jung The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops. (English) Zbl 1225.05113 Discrete Appl. Math. 158, No. 4, 319-330 (2010). MSC: 05C20 05C60 05C85 PDFBibTeX XMLCite \textit{G. Gutin} and \textit{E. J. Kim}, Discrete Appl. Math. 158, No. 4, 319--330 (2010; Zbl 1225.05113) Full Text: DOI
Heggernes, Pinar; Meister, Daniel; Papadopoulos, Charis A new representation of proper interval graphs with an application to clique-width. (English) Zbl 1267.05176 Koster, Arie (ed.) et al., DIMAP workshop on algorithmic graph theory. Extended abstracts from the workshop held at the University of Warwick, Coventry, UK, March 23–25, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 32, 27-34 (2009). MSC: 05C62 05C12 PDFBibTeX XMLCite \textit{P. Heggernes} et al., Electron. Notes Discrete Math. 32, 27--34 (2009; Zbl 1267.05176) Full Text: DOI
Kaplan, Haim; Nussbaum, Yahav Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs. (English) Zbl 1213.05248 Discrete Appl. Math. 157, No. 15, 3216-3230 (2009). MSC: 05C85 PDFBibTeX XMLCite \textit{H. Kaplan} and \textit{Y. Nussbaum}, Discrete Appl. Math. 157, No. 15, 3216--3230 (2009; Zbl 1213.05248) Full Text: DOI
Lin, Min Chih; Szwarcfiter, Jayme L. Characterizations and recognition of circular-arc graphs and subclasses: a survey. (English) Zbl 1228.05218 Discrete Math. 309, No. 18, 5618-5635 (2009). MSC: 05C62 05C38 05C85 05-02 PDFBibTeX XMLCite \textit{M. C. Lin} and \textit{J. L. Szwarcfiter}, Discrete Math. 309, No. 18, 5618--5635 (2009; Zbl 1228.05218) Full Text: DOI
Nešetřil, Jaroslav A surprising permanence of old motivations (a not-so-rigid story). (English) Zbl 1183.01032 Discrete Math. 309, No. 18, 5510-5526 (2009). Reviewer: Antonín Slavík (Praha) MSC: 01A70 05-02 05-03 05C75 PDFBibTeX XMLCite \textit{J. Nešetřil}, Discrete Math. 309, No. 18, 5510--5526 (2009; Zbl 1183.01032) Full Text: DOI
Saitoh, Toshiki; Yamanaka, Katsuhisa; Kiyomi, Masashi; Uehara, Ryuhei Random generation and enumeration of proper interval graphs. (English) Zbl 1211.68291 Das, Sandip (ed.) et al., WALCOM: Algorithms and computation. Third international workshop, WALCOM 2009, Kolkata, India, February 18–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00201-4/pbk). Lecture Notes in Computer Science 5431, 177-189 (2009). MSC: 68R10 05C30 05C85 PDFBibTeX XMLCite \textit{T. Saitoh} et al., Lect. Notes Comput. Sci. 5431, 177--189 (2009; Zbl 1211.68291) Full Text: DOI
Gutin, Gregory; Hell, Pavol; Rafiey, Arash; Yeo, Anders A dichotomy for minimum cost graph homomorphisms. (English) Zbl 1149.90164 Eur. J. Comb. 29, No. 4, 900-911 (2008). Reviewer: Rainer E. Burkard (Graz) MSC: 90C35 PDFBibTeX XMLCite \textit{G. Gutin} et al., Eur. J. Comb. 29, No. 4, 900--911 (2008; Zbl 1149.90164) Full Text: DOI
Corneil, Derek G. A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. (English) Zbl 1042.05067 Discrete Appl. Math. 138, No. 3, 371-379 (2004). MSC: 05C60 05C85 68R10 PDFBibTeX XMLCite \textit{D. G. Corneil}, Discrete Appl. Math. 138, No. 3, 371--379 (2004; Zbl 1042.05067) Full Text: DOI