×

Found 103 Documents (Results 1–100)

The complexity of multiple handed self-assembly. (English) Zbl 07553900

Kostitsyna, Irina et al., Unconventional computation and natural computation. 19th international conference, UCNC 2021, Espoo, Finland, October 18–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12984, 1-18 (2021).
PDFBibTeX XMLCite
Full Text: DOI

Counting 4-patterns in permutations is equivalent to counting 4-cycles in graphs. (English) Zbl 07765381

Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 23, 18 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

A fine-grained analogue of Schaefer’s theorem in P: dichotomy of \(\exists^k-\forall\)-quantified first-order graph properties. (English) Zbl 07564431

Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 31, 27 p. (2019).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width. (English) Zbl 07561702

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 58, 15 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithms and hardness for diameter in dynamic graphs. (English) Zbl 07561506

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 13, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Counting triangles under updates in worst-case optimal time. (English) Zbl 07561464

Barcelo, Pablo (ed.) et al., 22nd international conference on database theory, ICDT 2019, March 26–28, 2019, Lisbon, Portugal. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 127, Article 4, 18 p. (2019).
MSC:  68P15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tensor network complexity of multilinear maps. (English) Zbl 07559050

Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 7, 21 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Triangles and girth in disk graphs and transmission graphs. (English) Zbl 07525501

Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 64, 14 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fine-grained complexity of \(k\)-OPT in bounded-degree graphs for solving TSP. (English) Zbl 07525460

Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 23, 14 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Counting connected subgraphs with maximum-degree-aware sieving. (English) Zbl 07561371

Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 17, 12 p. (2018).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Efficient and adaptive parameterized algorithms on modular decompositions. (English) Zbl 1524.68235

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 55, 15 p. (2018).
MSC:  68R10 05C85 68W40
PDFBibTeX XMLCite
Full Text: DOI arXiv

QPTAS and subexponential algorithm for maximum clique on disk graphs. (English) Zbl 1489.68342

Speckmann, Bettina (ed.) et al., 34th international symposium on computational geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 99, Article 12, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Counting subgraphs in relational event graphs. (English) Zbl 1475.68234

Kaykobad, Mohammad (ed.) et al., WALCOM: algorithms and computation. 10th international workshop, WALCOM 2016, Kathmandu, Nepal, March 29–31, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9627, 194-206 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Subquadratic time approximation algorithms for the girth. (English) Zbl 1423.05183

Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 833-845 (2012).
PDFBibTeX XMLCite
Full Text: Link

On generating triangle-free graphs. (English) Zbl 1267.05246

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, 51-58 (2009).
MSC:  05C85 05C10
PDFBibTeX XMLCite
Full Text: DOI

Balanced hashing, color coding and approximate counting. (English) Zbl 1273.68270

Chen, Jianer (ed.) et al., Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10–11, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-11268-3/pbk). Lecture Notes in Computer Science 5917, 1-16 (2009).
PDFBibTeX XMLCite
Full Text: DOI

The \(h\)-index of a graph and its application to dynamic subgraph statistics. (English) Zbl 1253.68107

Dehne, Frank (ed.) et al., Algorithms and data structures. 11th international symposium, WADS 2009, Banff, Canada, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03366-7/pbk). Lecture Notes in Computer Science 5664, 278-289 (2009).
MSC:  68P05 68R10
PDFBibTeX XMLCite
Full Text: DOI

Efficient approximation algorithms for shortest cycles in undirected graphs. (English) Zbl 1136.68466

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, 736-746 (2008).
MSC:  68R10 68W25
PDFBibTeX XMLCite
Full Text: DOI

Detecting induced subgraphs. (English) Zbl 1341.05169

Márquez, Alberto (ed.) et al., Proceedings of the 4th European conference on combinatorics, graph theory and applications, EuroComb’07, Seville, Spain, September 11–15, 2007. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 29, 207-211 (2007).
MSC:  05C60
PDFBibTeX XMLCite
Full Text: DOI arXiv

An efficient algorithm for Helly property recognition in a linear hypergraph. (English) Zbl 1260.05157

Fourey, Sebastien (ed.) et al., IWCIA 2001. Proceedings of the 8th international workshop on combinatorial image analysis, Temple University, Philadelphia, PA, USA, August 23–24, 2001. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 46, 177-187 (2001).
MSC:  05C85 05C65 68Q17
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

all top 3

Software