×

Found 83 Documents (Results 1–83)

Algorithms and lower bounds for cycles and walks: small space and sparse graphs. (English) Zbl 07650359

Vidick, Thomas (ed.), 11th innovations in theoretical computer science conference, ITCS 2020, Seattle, Washington, USA, January 12–14, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 151, Article 11, 17 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

LaserTank is NP-complete. (English) Zbl 07441080

Slamanig, Daniel (ed.) et al., Mathematical aspects of computer and information sciences. 8th international conference, MACIS 2019, Gebze, Turkey, November 13–15, 2019. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 11989, 333-338 (2020).
MSC:  68-XX 65-XX
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tracking paths in planar graphs. (English) Zbl 07650287

Lu, Pinyan (ed.) et al., 30th international symposium on algorithms and computation, ISAAC 2019, Shanghai University of Finance and Economics, Shanghai, China, December 8–11, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 149, Article 54, 17 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Planar 3-SAT with a clause/variable cycle. (English) Zbl 1477.68294

Eppstein, David (ed.), 16th Scandinavian symposium and workshops on algorithm theory. SWAT 2018, June 18–20, 2018, Malmö University, Malmö, Sweden. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 101, Article 31, 13 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Weighted coloring in trees. (English) Zbl 1359.68115

Mayr, Ernst W. (ed.) et al., 31st international symposium on theoretical aspects of computer science, STACS’ 14, Lyon, France, March 5–8, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-65-1). LIPIcs – Leibniz International Proceedings in Informatics 25, 75-86 (2014).
PDFBibTeX XMLCite
Full Text: DOI

Short propositional refutations for dense random 3CNF formulas. (English) Zbl 1364.03082

Proceedings of the 2012 27th annual ACM/IEEE symposium on logic in computer science, LICS 2012, Dubrovnik, Croatia, June 25–28, 2012. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4769-5). 501-510 (2012).
MSC:  03F20 03B05
PDFBibTeX XMLCite
Full Text: DOI

On a DAG partitioning problem. (English) Zbl 1342.05109

Bonato, Anthony (ed.) et al., Algorithms and models for the web graph. 9th international workshop, WAW 2012, Halifax, NS, Canada, June 22–23, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-30540-5/pbk). Lecture Notes in Computer Science 7323, 17-28 (2012).
PDFBibTeX XMLCite
Full Text: DOI

A class of hypergraphs and vertices of cut polytope relaxations. (English. Russian original) Zbl 1244.05157

Dokl. Math. 85, No. 1, 46-47 (2012); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 442, No. 3, 300-302 (2012).
MSC:  05C65 52B99
PDFBibTeX XMLCite
Full Text: DOI

Improving PPSZ for 3-SAT using critical variables. (English) Zbl 1230.68179

Schwentick, Thomas (ed.) et al., STACS 2011. 28th international symposium on theoretical aspects of computer science, Dortmund, Germany, March 10–12, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-25-5). LIPIcs – Leibniz International Proceedings in Informatics 9, 237-248, electronic only (2011).
MSC:  68T20 68W20 68W40
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Improved randomized algorithms for 3-SAT. (English) Zbl 1310.68230

Cheong, Otfried (ed.) et al., Algorithms and computation. 21st international symposium, ISAAC 2010, Jeju Island, Korea, December 15–17, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-17516-9/pbk). Lecture Notes in Computer Science 6506, 73-84 (2010).
MSC:  68W20 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Minimum Manhattan network is NP-complete. (English) Zbl 1388.68287

Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8–10, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-501-7). 393-402 (2009).
PDFBibTeX XMLCite
Full Text: DOI Link

A new upper bound for 3-SAT. (English) Zbl 1248.68242

Hariharan, Ramesh (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2008), December 9–11, 2008, Bangalore, India. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-08-8). LIPIcs – Leibniz International Proceedings in Informatics 2, 163-174, electronic only (2008).
MSC:  68Q25 68T20 68Q87
PDFBibTeX XMLCite
Full Text: DOI Link

Hidden threshold phenomena for fixed-density SAT-formulae. (English) Zbl 1204.68214

Giunchiglia, Enrico (ed.) et al., Theory and applications of satisfiability testing. 6th international conference, SAT 2003, Santa Margherita Ligure, Italy, May 5–8, 2003. Selected revised papers. Berlin: Springer (ISBN 3-540-20851-8/pbk). Lect. Notes Comput. Sci. 2919, 135-149 (2004).
MSC:  68T20 05C15
PDFBibTeX XMLCite
Full Text: DOI

The unsatisfiability threshold revisited. (English) Zbl 0990.90557

Kautz, Henry (ed.) et al., LICS 2001 workshop on theory and application of satisfiability testing (SAT 2001). Boston, MA, USA, June 14-15, 2001. Amsterdam: Elsevier, Electron. Notes Discrete Math. 9, no pag., electronic only (2001).
MSC:  90C27 90B80
PDFBibTeX XMLCite

Statistical physics analysis of the backtrack resolution of random 3-SAT instances. (English) Zbl 0994.90513

Kautz, Henry (ed.) et al., LICS 2001 workshop on theory and application of satisfiability testing (SAT 2001). Boston, MA, USA, June 14-15, 2001. Amsterdam: Elsevier, Electron. Notes Discrete Math. 9, no pag., electronic only (2001).
MSC:  90C27
PDFBibTeX XMLCite

Typical random 3-SAT formulae and the satisfiability threshold. (English) Zbl 0959.68135

Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 9-11, 2000. Philadelphia, PA: SIAM. 126-127 (2000).
MSC:  68W05 68Q05
PDFBibTeX XMLCite

Solution to 3-SAT by breadth first search. (English) Zbl 0971.68062

Winfree, Erik (ed.) et al., DNA based computers V. DIMACS workshop, Massachusetts Institute of Technology, Cambridge, MA, USA, June 14-15, 1999. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 54, 9-22 (1999).
MSC:  68Q10 68P10 68W10
PDFBibTeX XMLCite

Worst-case analysis, 3-SAT decision and lower bounds: Approaches for improved SAT algorithms. (English) Zbl 0889.03030

Du, Dingzhu (ed.) et al., Satisfiability problem: theory and applications. DIMACS workshop, Piscataway, NJ, USA, March 11-13, 1996. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 35, 261-313 (1997).
PDFBibTeX XMLCite

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software