×

Found 189 Documents (Results 1–100)

Pairwise reachability oracles and preservers under failures. (English) Zbl 07870245

Bojańczyk, Mikołaj (ed.) et al., 49th EATCS international conference on automata, languages, and programming, ICALP 2022, Paris, France, July 4–8, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 229, Article 35, 16 p. (2022).
MSC:  68Nxx 68Qxx

Single-source shortest \(p\)-disjoint paths: fast computation and sparse preservers. (English) Zbl 07836579

Berenbrink, Petra (ed.) et al., 39th international symposium on theoretical aspects of computer science, STACS 2022, Marseille, France, virtual conference, March 15–18, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 219, Article 12, 21 p. (2022).
MSC:  68Qxx

Domain sparsification of discrete distributions using entropic independence. (English) Zbl 07829237

Braverman, Mark (ed.), 13th innovations in theoretical computer science conference, ITCS 2022, Berkeley, CA, USA, January 31 – February 3, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 215, Article 5, 23 p. (2022).
MSC:  68Qxx

Learning to sparsify travelling salesman problem instances. (English) Zbl 07493643

Stuckey, Peter J. (ed.), Integration of constraint programming, artificial intelligence, and operations research. 18th international conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12735, 410-426 (2021).
MSC:  68T20 90C27

A distributed algorithm for spectral sparsification of graphs with applications to data clustering. (English) Zbl 1483.68259

Gentile, Claudio (ed.) et al., Graphs and combinatorial optimization: from theory to applications. Proceedings of the 18th Cologne-Twente workshop on graphs and combinatorial optimization (CTW2020), online, September 14–16, 2020. Cham: Springer. AIRO Springer Ser. 5, 403-413 (2021).

Sparsification lower bounds for list \(H\)-coloring. (English) Zbl 07765416

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 58, 17 p. (2020).
MSC:  68Wxx

A simple algorithm for minimum cuts in near-linear time. (English) Zbl 07759280

Albers, Susanne (ed.), 17th Scandinavian symposium and workshops on algorithm theory, SWAT 2020, Tórshavn, Faroe Islands, June 22–24, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 162, Article 12, 18 p. (2020).
MSC:  68Wxx

Palette sparsification beyond \((\Delta +1)\) vertex coloring. (English) Zbl 07758308

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 6, 22 p. (2020).
MSC:  68W20 68W25 90C27

Augmenting the algebraic connectivity of graphs. (English) Zbl 07651209

Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 70, 22 p. (2020).
MSC:  68Wxx

Fault tolerant subgraphs with applications in kernelization. (English) Zbl 07650395

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 47, 22 p. (2020).
MSC:  68Qxx
Full Text: DOI

Best-case and worst-case sparsifiability of Boolean CSPs. (English) Zbl 1520.68177

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 15, 13 p. (2019).

Spanning tree congestion and computation of generalized Győri-Lovász partition. (English) Zbl 1499.68259

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 32, 14 p. (2018).

Edge estimation with independent set oracles. (English) Zbl 1462.68132

Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 38, 21 p. (2018).

Optimal data reduction for graph coloring using low-degree polynomials. (English) Zbl 1443.68132

Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 22, 12 p. (2018).
Full Text: DOI

Density independent algorithms for sparsifying \(k\)-step random walks. (English) Zbl 1467.05255

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 14, 17 p. (2017).

Sparsification enables predicting kissing hairpin pseudoknot structures of long RNAs in practice. (English) Zbl 1443.92140

Schwartz, Russell (ed.) et al., 17th international workshop on algorithms in bioinformatics, WABI 2017, Boston, MA, USA, August 21–23, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 88, Article 12, 13 p. (2017).
MSC:  92D20 92-08
Full Text: DOI

Improved guarantees for vertex sparsification in planar graphs. (English) Zbl 1442.68171

Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 44, 14 p. (2017).
Full Text: DOI

The impact of landscape sparsification on modelling and analysis of the invasion process. (English) Zbl 1436.92017

Iliopoulos, Costas S. (ed.) et al., 16th international symposium on experimental algorithms, SEA 2017, London, UK, June 21–23, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 75, Article 32, 16 p. (2017).
MSC:  92D40 92C42
Full Text: DOI

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