×

Found 84 Documents (Results 1–84)

Testing upward planarity of partial 2-trees. (English) Zbl 07727760

Angelini, Patrizio (ed.) et al., Graph drawing and network visualization. 30th international symposium, GD 2022, Tokyo, Japan, September 13–16, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13764, 175-187 (2023).
MSC:  68R10 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts. (English) Zbl 07682404

Bekos, Michael A. (ed.) et al., Graph-theoretic concepts in computer science. 48th international workshop, WG 2022, Tübingen, Germany, June 22–24, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13453, 98-113 (2022).
MSC:  68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

47th international symposium on mathematical foundations of computer science, MFCS 2022, Vienna, Austria, August 22–26, 2022. (English) Zbl 1496.68034

LIPIcs – Leibniz International Proceedings in Informatics 241. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik (ISBN 978-3-95977-256-3). xvii, 83 articles, not consecutively paged, electronic only, open access (2022).
MSC:  68-06 68Qxx 00B25
PDFBibTeX XMLCite
Full Text: DOI Link

On covering segments with unit intervals. (English) Zbl 07650898

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 13, 17 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Extending nearly complete \(1\)-planar drawings in polynomial time. (English) Zbl 07559402

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 31, 16 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized algorithms for queue layouts. (English) Zbl 07436606

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, 40-54 (2020).
MSC:  68R10 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Measuring what matters: a hybrid approach to dynamic programming with treewidth. (English) Zbl 1517.68292

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 42, 15 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI

Group activity selection with few agent types. (English) Zbl 07525485

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 48, 16 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized algorithms for book embedding problems. (English) Zbl 1482.68170

Archambault, Daniel (ed.) et al., Graph drawing and network visualization. 27th international symposium, GD 2019, Prague, Czech Republic, September 17–20, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11904, 365-378 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On strict (outer-)confluent graphs. (English) Zbl 07266113

Archambault, Daniel (ed.) et al., Graph drawing and network visualization. 27th international symposium, GD 2019, Prague, Czech Republic, September 17–20, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11904, 147-161 (2019).
MSC:  68R10 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

The power of cut-based parameters for computing edge disjoint paths. (English) Zbl 1512.68219

Sau, Ignasi (ed.) et al., Graph-theoretic concepts in computer science. 45th international workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019. Revised papers. Cham: Springer. Lect. Notes Comput. Sci. 11789, 190-204 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

SAT-encodings for treecut width and treedepth. (English) Zbl 1430.68206

Kobourov, Stephen (ed.) et al., Proceedings of the 21st workshop on algorithm engineering and experiments, ALENEX ’19, San Diego, CA, USA, January 7–8, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 117-129 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On structural parameterizations of the bounded-degree vertex deletion problem. (English) Zbl 1487.68177

Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 33, 14 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Small resolution proofs for QBF using dependency treewidth. (English) Zbl 1487.68135

Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 28, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On structural parameterizations of the edge disjoint paths problem. (English) Zbl 1457.68215

Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 36, 13 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Towards a polynomial kernel for directed feedback vertex set. (English) Zbl 1441.68163

Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 36, 15 p. (2017).
MSC:  68R10 05C85 68Q27
PDFBibTeX XMLCite
Full Text: DOI

Combining treewidth and backdoors for CSP. (English) Zbl 1402.68094

Vollmer, Heribert (ed.) et al., 34th symposium on theoretical aspects of computer science (STACS 2017), Hannover, Germany, March 8–11, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-028-6). LIPIcs – Leibniz International Proceedings in Informatics 66, Article 36, 17 p. (2017).
MSC:  68Q25 68W05
PDFBibTeX XMLCite
Full Text: DOI arXiv

New width parameters for model counting. (English) Zbl 1496.68257

Gaspers, Serge (ed.) et al., Theory and applications of satisfiability testing – SAT 2017. 20th international conference, Melbourne, VIC, Australia, August 28 – September 1, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10491, 38-52 (2017).
MSC:  68R07 68Q27
PDFBibTeX XMLCite
Full Text: DOI

Backdoor treewidth for SAT. (English) Zbl 1496.68256

Gaspers, Serge (ed.) et al., Theory and applications of satisfiability testing – SAT 2017. 20th international conference, Melbourne, VIC, Australia, August 28 – September 1, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10491, 20-37 (2017).
MSC:  68R07 68Q27
PDFBibTeX XMLCite
Full Text: DOI

Discovering archipelagos of tractability for constraint satisfaction and counting. (English) Zbl 1410.68166

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1670-1681 (2016).
MSC:  68Q25 68T20
PDFBibTeX XMLCite
Full Text: DOI

On existential MSO and its relation to ETH. (English) Zbl 1398.68179

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 42, 14 p. (2016).
MSC:  68Q15 03B15
PDFBibTeX XMLCite
Full Text: DOI

On the complexity landscape of connected \(f\)-factor problems. (English) Zbl 1398.68233

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 41, 14 p. (2016).
MSC:  68Q25 05C40 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. (English) Zbl 1398.68228

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 34, 14 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Counting linear extensions: parameterizations by treewidth. (English) Zbl 1397.68098

Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 39, 18 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Meta-kernelization using well-structured modulators. (English) Zbl 1378.68073

Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 114-126 (2015).
MSC:  68Q25 68W05
PDFBibTeX XMLCite
Full Text: DOI

Community structure inspired algorithms for SAT and #SAT. (English) Zbl 1471.68322

Heule, Marijn (ed.) et al., Theory and applications of satisfiability testing – SAT 2015. 18th international conference, Austin, TX, USA, September 24–27, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9340, 223-237 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Solving problems on graphs of high rank-width. (English) Zbl 1392.68199

Dehne, Frank (ed.) et al., Algorithms and data structures. 14th international symposium, WADS 2015, Victoria, BC, Canada, August 5–7, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-21839-7/pbk; 978-3-319-21840-3/ebook). Lecture Notes in Computer Science 9214, 314-326 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized complexity of asynchronous border minimization. (English) Zbl 1459.68085

Jain, Rahul (ed.) et al., Theory and applications of models of computation. 12th annual conference, TAMC 2015, Singapore, May 18–20, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9076, 428-440 (2015).
MSC:  68Q27 68Q17 92-08
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithmic applications of tree-cut width. (English) Zbl 1465.68211

Italiano, F. (ed.) et al., Mathematical foundations of computer science 2015. 40th international symposium, MFCS 2015, Milan, Italy, August 24–28, 2015. Proceedings. Part II. Berlin: Springer. Lect. Notes Comput. Sci. 9235, 348-360 (2015).
MSC:  68R10 68Q17 68Q27
PDFBibTeX XMLCite
Full Text: DOI

Model checking existential logic on partially ordered sets. (English) Zbl 1401.68187

Proceedings of the joint meeting of the twenty-third EACSL annual conference on computer science logic, CSL, and the 2014 29th annual ACM/IEEE symposium on logic in computer science, LICS 2014, Vienna, Austria, July 14–18, 2014. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4503-2886-9). Paper No. 21, 10 p. (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quantified conjunctive queries on partially ordered sets. (English) Zbl 1456.68096

Cygan, Marek (ed.) et al., Parameterized and exact computation. 9th international symposium, IPEC 2014, Wroclaw, Poland, September 10–12, 2014. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8894, 122-134 (2014).
MSC:  68Q60 06A06 68Q27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Expanding the expressive power of monadic second-order logic on restricted graph classes. (English) Zbl 1284.68463

Lecroq, Thierry (ed.) et al., Combinatorial algorithms. 24th international workshop, IWOCA 2013, Rouen, France, July 10–12, 2013. Revised selected papers. Berlin: Springer (ISBN 978-3-642-45277-2/pbk). Lecture Notes in Computer Science 8288, 164-177 (2013).
MSC:  68R10 03B15 03B70 68Q17 68Q25 68Q60
PDFBibTeX XMLCite
Full Text: DOI arXiv

Meta-kernelization with structural parameters. (English) Zbl 1400.68089

Chatterjee, Krishnendu (ed.) et al., Mathematical foundations of computer science 2013. 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40312-5/pbk). Lecture Notes in Computer Science 8087, 457-468 (2013).
MSC:  68Q25 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

FO model checking of interval graphs. (English) Zbl 1334.68132

Fomin, Fedor V. (ed.) et al., Automata, languages, and programming. 40th international colloquium, ICALP 2013, Riga, Latvia, July 8–12, 2013, Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-39211-5/pbk). Lecture Notes in Computer Science 7966, 250-262 (2013).
MSC:  68Q60 68Q25 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\). (English) Zbl 1365.68323

Rovan, Branislav (ed.) et al., Mathematical foundations of computer science 2012. 37th international symposium, MFCS 2012, Bratislava, Slovakia, August 27–31, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32588-5/pbk). Lecture Notes in Computer Science 7464, 419-430 (2012).
MSC:  68Q60 03B15 05C05 05C75 68R10
PDFBibTeX XMLCite
Full Text: DOI

Lower bounds on the complexity of \(\mathrm{MSO}_1\) model-checking. (English) Zbl 1245.68107

Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th – March 3rd, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-35-4). LIPIcs – Leibniz International Proceedings in Informatics 14, 326-337, electronic only (2012).
PDFBibTeX XMLCite
Full Text: DOI

Twin-cover: beyond vertex cover in parameterized algorithmics. (English) Zbl 1352.68105

Marx, Dániel (ed.) et al., Parameterized and exact computation. 6th international symposium, IPEC 2011, Saarbrücken, Germany, September 6–8, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28049-8/pbk). Lecture Notes in Computer Science 7112, 259-271 (2012).
MSC:  68Q25 05C70 05C85
PDFBibTeX XMLCite
Full Text: DOI

Clique-width: when hard does not mean impossible. (English) Zbl 1230.68109

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, 404-415, electronic only (2011).
PDFBibTeX XMLCite
Full Text: DOI Link

Thread graphs, linear rank-width and their algorithmic applications. (English) Zbl 1295.68172

Iliopoulos, Costas S. (ed.) et al., Combinatorial algorithms. 21st international workshop, IWOCA 2010, London, UK, July 26–28, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-19221-0/pbk). Lecture Notes in Computer Science 6460, 38-42 (2011).
MSC:  68R10 05C85
PDFBibTeX XMLCite
Full Text: DOI

New results on the complexity of the Max- and Min-Rep problems. (English) Zbl 1298.68112

Černá, Ivana (ed.) et al., SOFSEM 2011: Theory and practice of computer science. 37th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 22–28, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-18380-5/pbk). Lecture Notes in Computer Science 6543, 238-247 (2011).
MSC:  68Q25 05C35
PDFBibTeX XMLCite
Full Text: DOI

Better algorithms for satisfiability problems for formulas of bounded rank-width. (English) Zbl 1245.68108

Lodaya, Kamal (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2010), December 15–18, 2010, Chennai, India. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-23-1). LIPIcs – Leibniz International Proceedings in Informatics 8, 73-83, electronic only (2010).
MSC:  68Q25 68R10 68T20
PDFBibTeX XMLCite
Full Text: DOI Link

Are there any good digraph width measures? (English) Zbl 1309.68150

Raman, Venkatesh (ed.) et al., Parameterized and exact computation. 5th international symposium, IPEC 2010, Chennai, India, December 13–15, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-17492-6/pbk). Lecture Notes in Computer Science 6478, 135-146 (2010).
PDFBibTeX XMLCite
Full Text: DOI arXiv

New results on the complexity of oriented colouring on restricted digraph classes. (English) Zbl 1274.68138

van Leeuwen, Jan (ed.) et al., SOFSEM 2010: Theory and practice of computer science. 36th conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 23–29, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-11265-2/pbk). Lecture Notes in Computer Science 5901, 428-439 (2010).
MSC:  68Q25 05C15 05C20
PDFBibTeX XMLCite
Full Text: DOI

The parameterized complexity of oriented colouring. (English) Zbl 1247.68098

Hlinený, Petr (ed.) et al., Annual doctoral workshop on mathematical and engineering methods in computer science (MEMICS’09). Selected papers based on the presentations at the workshop, November 13-15, 2009, Znojmo, Czech Republic. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-15-6). OASIcs – OpenAccess Series in Informatics 13, 86-93, electronic only (2009).
MSC:  68Q17 05C15 05C85
PDFBibTeX XMLCite
Full Text: DOI

On digraph width measures in parameterized algorithmics. (English) Zbl 1273.68276

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, 185-197 (2009).
MSC:  68R10 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field

Software