×

Found 103 Documents (Results 1–100)

Min orderings and list homomorphism dichotomies for signed and unsigned graphs. (English) Zbl 07719364

Castañeda, Armando (ed.) et al., Latin 2022: theoretical informatics. 15th Latin American symposium, Guanajuato, Mexico, November 7–11, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13568, 510-526 (2022).
MSC:  68Qxx 68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

List homomorphisms to separable signed graphs. (English) Zbl 07683160

Balachandran, Niranjan (ed.) et al., Algorithms and discrete applied mathematics. 8th international conference, CALDAM 2022, Puducherry, India, February 10–12, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13179, 22-35 (2022).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

On the kernel and related problems in interval digraphs. (English) Zbl 07788590

Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 17, 17 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Template-driven rainbow coloring of proper interval graphs. (English) Zbl 07497552

Mudgal, Apurva (ed.) et al., Algorithms and discrete applied mathematics. 7th international conference, CALDAM 2021, Rupnagar, India, February 11–13, 2021. Proceedings. Lect. Notes Comput. Sci. 12601, 452-470 (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

List homomorphism problems for signed graphs. (English) Zbl 07559391

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 20, 14 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Interval-like graphs and digraphs. (English) Zbl 1494.68195

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 68, 13 p. (2018).
MSC:  68R10 05C85
PDFBibTeX XMLCite
Full Text: DOI arXiv

Correspondence homomorphisms to reflexive graphs. (English) Zbl 1383.05212

Bassino, Frédérique (ed.) et al., LAGOS 2017. Selected papers of the 9th Latin-American algorithms, graphs, and optimization symposium, Marseille, France, September 11–15, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 62, 9-14 (2017).
MSC:  05C60 05C15 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Minimum cost homomorphisms with constrained costs. (English) Zbl 1476.68110

Dinh, Thang N. (ed.) et al., Computing and combinatorics. 22nd international conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2–4, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9797, 194-206 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy. (English) Zbl 1401.68104

Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 487-498 (2015).
MSC:  68Q19 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm. (English) Zbl 1371.05244

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1708-1727 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Space complexity of list \(H\)-colouring: a dichotomy. (English) Zbl 1421.68073

Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 349-365 (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithmic aspects in information and management. 10th international conference, AAIM 2014, Vancouver, BC, Canada, July 8–11, 2014. Proceedings. (English) Zbl 1309.68009

Lecture Notes in Computer Science 8546. Berlin: Springer (ISBN 978-3-319-07955-4/pbk). xvi, 342 p. (2014).
PDFBibTeX XMLCite
Full Text: DOI

Intersection dimension of bipartite graphs. (English) Zbl 1406.05084

Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 11th annual conference, TAMC 2014, Chennai, India, April 11–13, 2014. Proceedings. Berlin: Springer (ISBN 978-3-319-06088-0/pbk). Lecture Notes in Computer Science 8402, 323-340 (2014).
MSC:  05C75 05C62 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Complexity of coloring graphs without paths and cycles. (English) Zbl 1405.68140

Pardo, Alberto (ed.) et al., LATIN 2014: theoretical informatics. 11th Latin American symposium, Montevideo, Uruguay, March 31 – April 4, 2014. Proceedings. Berlin: Springer (ISBN 978-3-642-54422-4/pbk). Lecture Notes in Computer Science 8392, 538-549 (2014).
MSC:  68Q25 05C15 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Small \(H\)-coloring problems for bounded degree digraphs. (English) Zbl 1382.68111

Du, Ding-Zhu (ed.) et al., Computing and combinatorics. 19th international conference, COCOON 2013, Hangzhou, China, June 21–23, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38767-8/pbk). Lecture Notes in Computer Science 7936, 579-590 (2013).
MSC:  68Q25 05C15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Counting partitions of graphs. (English) Zbl 1260.68176

Chao, Kun-Mao (ed.) et al., Algorithms and computation. 23rd international symposium, ISAAC 2012, Taipei, Taiwan, December 19–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-35260-7/pbk). Lecture Notes in Computer Science 7676, 227-236 (2012).
MSC:  68Q25 05C70 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Approximation of minimum cost homomorphisms. (English) Zbl 1365.05203

Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 587-598 (2012).
PDFBibTeX XMLCite
Full Text: DOI

The dichotomy of list homomorphisms for digraphs. (English) Zbl 1376.68067

Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1703-1713 (2011).
PDFBibTeX XMLCite
Full Text: Link

Faithful representations of graphs by islands in the extended grid. (English) Zbl 1283.68269

López-Ortiz, Alejandro (ed.), LATIN 2010: Theoretical informatics. 9th Latin American symposium, Oaxaca, Mexico, April 19–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-12199-9/pbk). Lecture Notes in Computer Science 6034, 131-142 (2010).
MSC:  68R10
PDFBibTeX XMLCite
Full Text: DOI

On injective colourings of chordal graphs. (English) Zbl 1136.68463

Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 520-530 (2008).
PDFBibTeX XMLCite
Full Text: DOI

Minimum cost homomorphisms to reflexive digraphs. (English) Zbl 1136.68462

Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 182-193 (2008).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Two algorithms for general list matrix partitions. (English) Zbl 1297.68091

Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 870-876 (2005).
MSC:  68Q25 05C70 05C85
PDFBibTeX XMLCite

List partitions of chordal graphs. (English) Zbl 1196.05060

Farach-Colton, Martin (ed.), LATIN 2004: Theoretical informatics. 6th Latin American symposium, Buenos Aires, Argentina, April 5–8, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21258-2/pbk). Lecture Notes in Computer Science 2976, 100-108 (2004).
MSC:  05C69 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Counting list homomorphisms for graphs with bounded degrees. (English) Zbl 1059.05049

Nešetřil, J. (ed.) et al., Graphs, morphisms and statistical physics. Proceedings of the workshop held at Rutgers University, Piscataway, NJ, USA, March 19–21, 2001. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3551-3/hbk). DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 63, 105-112 (2004).
MSC:  05C15 05C85 68R10
PDFBibTeX XMLCite

Algorithmic aspects of graph homomorphisms. (English) Zbl 1035.05089

Wensley, C. D. (ed.), Surveys in combinatorics, 2003. Proceedings of the 19th British combinatorial conference, University of Wales, Bangor, UK, June 29–July 04, 2003. Cambridge: Cambridge University Press (ISBN 0-521-54012-7/pbk). Lond. Math. Soc. Lect. Note Ser. 307, 239-276 (2003).
MSC:  05C85 05C15 68R05
PDFBibTeX XMLCite

Spanning trees with bounded number of branch vertices. (English) Zbl 1056.68587

Widmayer, Peter (ed.) et al., Automata, languages and programming. 29th international colloquium, ICALP 2002, Málaga, Spain, July 8–13, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43864-5). Lect. Notes Comput. Sci. 2380, 355-365 (2002).
PDFBibTeX XMLCite
Full Text: Link

Complexity of graph partition problems. (English) Zbl 1345.68171

Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 464-472 (1999).
PDFBibTeX XMLCite
Full Text: DOI

Colouring paths in directed symmetric trees with applications to WDM routing. (English) Zbl 1401.68245

Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7–11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 505-515 (1997).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Software