×

Found 1,768 Documents (Results 1–100)

Algorithms and complexity of strongly stable non-crossing matchings. (English) Zbl 07728676

Bagchi, Amitabha (ed.) et al., Algorithms and discrete applied mathematics. 9th international conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13947, 363-376 (2023).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

The complexity of growing a graph. (English) Zbl 07722896

Erlebach, Thomas (ed.) et al., Algorithmics of wireless networks. 18th international symposium on algorithmics of wireless networks, ALGOSENSORS 2022, Potsdam, Germany, September 8–9, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13707, 123-137 (2022).
MSC:  68M18 68T40
PDFBibTeX XMLCite
Full Text: DOI arXiv

Hardness and approximation results for some variants of stable marriage problem. (English) Zbl 07683177

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, 252-264 (2022).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Maximum cut on interval graphs of interval count four Is NP-complete. (English) Zbl 07724211

Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 38, 15 p. (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Computational complexity of two pencil puzzles: Kurotto and Juosan. (English) Zbl 07670967

Akiyama, Jin (ed.) et al., Discrete and computational geometry, graphs, and games. 21st Japanese conference, JCDCGGG 2018, Quezon City, Philippines, September 1–3, 2018. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13034, 175-185 (2021).
MSC:  68R10 68U05 91A80
PDFBibTeX XMLCite
Full Text: DOI

On the complexity of jelly-no-puzzle. (English) Zbl 07670966

Akiyama, Jin (ed.) et al., Discrete and computational geometry, graphs, and games. 21st Japanese conference, JCDCGGG 2018, Quezon City, Philippines, September 1–3, 2018. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13034, 165-174 (2021).
MSC:  68R10 68U05 91A80
PDFBibTeX XMLCite
Full Text: DOI

Hardness results of connected power domination for bipartite graphs and chordal graphs. (English) Zbl 07550559

Du, Ding-Zhu (ed.) et al., Combinatorial optimization and applications. 15th international conference, COCOA 2021, Tianjin, China, December 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13135, 653-667 (2021).
MSC:  68T20 90C27
PDFBibTeX XMLCite
Full Text: DOI

NP-completeness, proof systems, and disjoint NP-pairs. (English) Zbl 07650894

Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 9, 18 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

LP-based algorithms for computing maximum vertex-disjoint paths with different colors. (English) Zbl 07636428

Chen, Jianer (ed.) et al., Theory and applications of models of computation. 16th international conference, TAMC 2020, Changsha, China, October 18–20, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12337, 107-118 (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

On finding shortest paths in arc-dependent networks. (English) Zbl 1458.90628

Baïou, Mourad (ed.) et al., Combinatorial optimization. 6th international symposium, ISCO 2020, Montreal, QC, Canada, May 4–6, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12176, 249-260 (2020).
MSC:  90C35
PDFBibTeX XMLCite
Full Text: DOI

P-optimal proof systems for each NP-set but no complete disjoint NP-pairs relative to an oracle. (English) Zbl 07561691

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 47, 14 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Two moves per time step make a difference. (English) Zbl 07561634

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 141, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Deciding whether a grid is a topological subgraph of a planar graph is NP-complete. (English) Zbl 07515210

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, 545-556 (2019).
MSC:  05Cxx 90Cxx
PDFBibTeX XMLCite
Full Text: DOI

Complexity and algorithms for semipaired domination in graphs. (English) Zbl 1503.68222

Colbourn, Charles J. (ed.) et al., Combinatorial algorithms. 30th international workshop, IWOCA 2019, Pisa, Italy, July 23–25, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11638, 278-289 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software