×

Found 664 Documents (Results 1–100)

100
MathJax

Parameterized complexity of locally minimal defensive alliances. (English) Zbl 07497527

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, 135-148 (2021).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Characterizing Tseitin-formulas with short regular resolution refutations. (English) Zbl 07495569

Li, Chu-Min (ed.) et al., Theory and applications of satisfiability testing – SAT 2021. 24th international conference, Barcelona, Spain, July 5–9, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12831, 116-133 (2021).
MSC:  68Q25 68R07 68T20
PDF BibTeX XML Cite
Full Text: DOI

On the impact of treewidth in the computational complexity of freezing dynamics. (English) Zbl 07495174

De Mol, Liesbeth (ed.) et al., Connecting with computability. 17th conference on computability in Europe, CiE 2021, virtual event, Ghent, Belgium, July 5–9, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12813, 260-272 (2021).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Computing \(L(p, 1)\)-labeling with combined parameters. (English) Zbl 07405963

Uehara, Ryuhei (ed.) et al., WALCOM: algorithms and computation. 15th international conference and workshops, WALCOM 15, Yangon, Myanmar, February 28 – March 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12635, 208-220 (2021).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes. (English) Zbl 07405958

Uehara, Ryuhei (ed.) et al., WALCOM: algorithms and computation. 15th international conference and workshops, WALCOM 15, Yangon, Myanmar, February 28 – March 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12635, 142-153 (2021).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs. (English) Zbl 07393895

Comput. Complexity 30, No. 2, Paper No. 13, 74 p. (2021); correction ibid. 30, No. 2, Paper No. 16, 2 p. (2021).
MSC:  03F20 68Q17
PDF BibTeX XML Cite
Full Text: DOI

On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines. (English. Russian original) Zbl 1470.90040

Proc. Steklov Inst. Math. 313, Suppl. 1, S58-S72 (2021); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 26, No. 2, 108-124 (2020).
PDF BibTeX XML Cite
Full Text: DOI

The local queue number of graphs with bounded treewidth. (English) Zbl 07436605

Auber, David (ed.) et al., Graph drawing and network visualization. 28th international symposium, GD 2020, Vancouver, BC, Canada, September 16–18, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12590, 26-39 (2020).
MSC:  68R10 68U05
PDF BibTeX XML Cite
Full Text: DOI arXiv

Succinct monotone circuit certification: planarity and parameterized complexity. (English) Zbl 07336129

Kim, Donghyun (ed.) et al., Computing and combinatorics. 26th international conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12273, 496-507 (2020).
MSC:  68Rxx
PDF BibTeX XML Cite
Full Text: DOI

Lower bounds for QBFs of bounded treewidth. (English) Zbl 07299485

Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM). 410-424 (2020).
MSC:  03B70
PDF BibTeX XML Cite
Full Text: DOI arXiv

Minimum conflict free colouring parameterized by treewidth. (English) Zbl 1453.68094

Changat, Manoj (ed.) et al., Algorithms and discrete applied mathematics. 6th international conference, CALDAM 2020, Hyderabad, India, February 13–15, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12016, 439-450 (2020).
PDF BibTeX XML Cite
Full Text: DOI

On the parameterized complexity of spanning trees with small vertex covers. (English) Zbl 1453.68096

Changat, Manoj (ed.) et al., Algorithms and discrete applied mathematics. 6th international conference, CALDAM 2020, Hyderabad, India, February 13–15, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12016, 427-438 (2020).
PDF BibTeX XML Cite
Full Text: DOI

Bisection of bounded treewidth graphs by convolutions. (English) Zbl 07525479

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 42, 11 p. (2019).
MSC:  68Wxx
PDF BibTeX XML Cite
Full Text: DOI

On Tuza’s conjecture for triangulations and graphs with small treewidth. (English) Zbl 07515178

Coutinho, Gabriel (ed.) et al., Proceedings of LAGOS 2019, the tenth Latin and American algorithms, graphs and optimization symposium, Belo Horizonte, Brazil, June 2–7 2019. Amsterdam: Elsevier. Electron. Notes Theor. Comput. Sci. 346, 171-183 (2019).
MSC:  05Cxx 90Cxx
PDF BibTeX XML Cite
Full Text: DOI

Multivariate analysis of orthogonal range searching and graph distances. (English) Zbl 07378590

Paul, Christophe (ed.) et al., 13th international symposium on parameterized and exact computation, IPEC 2018, August 22–24, 2018, Helsinki, Finland. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 115, Article 4, 13 p. (2019).
MSC:  68Q25 68Wxx
PDF BibTeX XML Cite
Full Text: DOI

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Classification

Biographic Reference