Linear time solvable optimization problems on graphs of bounded clique-width. Zbl 1009.68102
Courcelle, B.; Makowsky, J. A.; Rotics, U. |
|
2000
|
Polynomial closure and unambiguous product. Zbl 0872.68119
Pin, J.-E.; Weil, P. |
|
1997
|
Compressed suffix trees with full functionality. Zbl 1148.68015
Sadakane, Kunihiko |
|
2007
|
Graph-modeled data clustering: Exact algorithms for clique generation. Zbl 1084.68117
Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf |
|
2005
|
Upper and lower bounds for randomized search heuristics in black-box optimization. Zbl 1103.68115
Droste, Stefan; Jansen, Thomas; Wegener, Ingo |
|
2006
|
On covering problems of codes. Zbl 0868.94056
Frances, M.; Litman, A. |
|
1997
|
Generating shorter bases for hard random lattices. Zbl 1217.94092
Alwen, Joël; Peikert, Chris |
|
2011
|
On short paths interdiction problems: Total and node-wise limited interdiction. Zbl 1148.68036
Boros, Endre; Borys, Konrad; Elbassioni, Khaled; Gurvich, Vladimir; Rudolf, Gabor; Zhao, Jihui |
|
2008
|
Fixed-parameter algorithms for cluster vertex deletion. Zbl 1205.68263
Hüffner, Falk; Komusiewicz, Christian; Moser, Hannes; Niedermeier, Rolf |
|
2010
|
Finite presentations of infinite structures: Automata and interpretations. Zbl 1061.03038
Blumensath, Achim; Grädel, Erich |
|
2004
|
Fixed points, Nash equilibria, and the existential theory of the reals. Zbl 1362.68088
Schaefer, Marcus; Štefankovič, Daniel |
|
2017
|
Network design with weighted players. Zbl 1176.91003
Chen, Ho-Lin; Roughgarden, Tim |
|
2009
|
Crown structures for vertex cover kernelization. Zbl 1148.68035
Abu-Khzam, Faisal N.; Fellows, Michael R.; Langston, Michael A.; Suters, W. Henry |
|
2007
|
Approximate equilibria and ball fusion. Zbl 1101.68336
Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul |
|
2003
|
Balanced graph partitioning. Zbl 1113.68069
Andreev, Konstantin; Räcke, Harald |
|
2006
|
Parameterized complexity of Vertex Cover variants. Zbl 1147.68607
Guo, Jiong; Niedermeier, Rolf; Wernicke, Sebastian |
|
2007
|
Numeration systems on a regular language. Zbl 0969.68095
Lecomte, P. B. A.; Rigo, M. |
|
2001
|
On edge irregular total labeling of categorical product of two cycles. Zbl 1284.05232
Ahmad, Ali; Bača, Martin; Siddiqui, Muhammad Kamran |
|
2014
|
Clique-width for 4-vertex forbidden subgraphs. Zbl 1103.68088
Brandstädt, Andreas; Engelfriet, Joost; Le, Hoang-Oanh; Lozin, Vadim V. |
|
2006
|
The efficiency of fair division. Zbl 1262.91099
Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria |
|
2012
|
Applying modular decomposition to parameterized cluster editing problems. Zbl 1179.68111
Protti, Fábio; Dantas da Silva, Maise; Szwarcfiter, Jayme Luiz |
|
2009
|
Nearest common ancestors: a survey and a new algorithm for a distributed environment. Zbl 1093.68136
Alstrup, Stephen; Gavoille, Cyril; Kaplan, Haim; Rauhe, Theis |
|
2004
|
A fast branching algorithm for cluster vertex deletion. Zbl 1336.68192
Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin |
|
2016
|
Undecidable problems for probabilistic automata of fixed dimension. Zbl 1039.68061
Blondel, Vincent D.; Canterini, Vincent |
|
2003
|
Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter. Zbl 1286.68196
Jansen, Bart M. P.; Bodlaender, Hans L. |
|
2013
|
Exact complexity of the winner problem for Young elections. Zbl 1061.90084
Rothe, Jörg; Spakowski, Holger; Vogel, Jörg |
|
2003
|
A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Zbl 0896.68080
Staiger, L. |
|
1998
|
Constant thresholds can make target set selection tractable. Zbl 1319.68109
Chopin, Morgan; Nichterlein, André; Niedermeier, Rolf; Weller, Mathias |
|
2014
|
Irregular total labellings of generalized Petersen graphs. Zbl 1254.05172
Haque, Khandoker Mohammed Mominul |
|
2012
|
Accessing nearby copies of replicated objects in a distributed environment. Zbl 0929.68126
Plaxton, C. G.; Rajaraman, R.; Richa, A. W. |
|
1999
|
Algebraic results on quantum automata. Zbl 1101.68029
Ambainis, Andris; Beaudry, Martin; Golovkins, Marats; Kikusts, Arnolds; Mercer, Mark; Therien, Denis |
|
2006
|
The complexity ecology of parameters: An illustration using bounded max leaf number. Zbl 1184.05123
Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Mnich, Matthias; Rosamond, Frances; Saurabh, Saket |
|
2009
|
Complexity of Presburger arithmetic with fixed quantifier dimension. Zbl 0872.68048
Schöning, U. |
|
1997
|
Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Zbl 1148.68041
Mölle, Daniel; Richter, Stefan; Rossmanith, Peter |
|
2008
|
Equational elements in additive algebras. Zbl 0914.68118
Bozapalidis, S. |
|
1999
|
First- and second-order diffusive methods for rapid, coarse, distributed load balancing. Zbl 0904.68137
Muthukrishnan, S.; Ghosh, B.; Schultz, M. H. |
|
1998
|
On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109
Berman, P.; Fujito, T. |
|
1999
|
Space efficient hash tables with worst case constant access time. Zbl 1066.68025
Fotakis, Dimitris; Pagh, Rasmus; Sanders, Peter; Spirakis, Paul |
|
2005
|
Nash equilibria and the price of anarchy for flows over time. Zbl 1278.91027
Koch, Ronald; Skutella, Martin |
|
2011
|
The complexity of equality constraint languages. Zbl 1148.68025
Bodirsky, Manuel; Kára, Jan |
|
2008
|
The complexity of optimal design of temporally connected graphs. Zbl 1379.68250
Akrida, Eleni C.; Gąsieniec, Leszek; Mertzios, George B.; Spirakis, Paul G. |
|
2017
|
A cubic kernel for feedback vertex set and loop cutset. Zbl 1215.68170
Bodlaender, Hans L.; van Dijk, Thomas C. |
|
2010
|
Local MST computation with short advice. Zbl 1213.68123
Fraigniaud, Pierre; Korman, Amos; Lebhar, Emmanuelle |
|
2010
|
Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. Zbl 1179.68055
Gradwohl, Ronen; Naor, Moni; Pinkas, Benny; Rothblum, Guy N. |
|
2009
|
New graph classes of bounded clique-width. Zbl 1084.68088
Brandstädt, Andreas; Dragan, Feodor F.; Le, Hoàng-Oanh; Mosca, Raffaele |
|
2005
|
Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327
Jeż, Artur; Okhotin, Alexander |
|
2010
|
The linear arrangement problem parameterized above guaranteed value. Zbl 1148.68039
Gutin, Gregory; Rafiey, Arash; Szeider, Stefan; Yeo, Anders |
|
2007
|
An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem. Zbl 1148.68037
Dehne, Frank; Fellows, Michael; Langston, Michael; Rosamond, Frances; Stevens, Kim |
|
2007
|
A generalization of Cobham’s theorem. Zbl 0895.68081
Durand, F. |
|
1998
|
\(\frac{13}{9}\)-approximation for graphic TSP. Zbl 1319.68255
Mucha, Marcin |
|
2014
|
The power of commuting with finite sets of words. Zbl 1121.68065
Kunc, Michal |
|
2007
|
Correspondence principles for effective dimensions. Zbl 1084.68054
Hitchcock, John M. |
|
2005
|
Dynamic programming for minimum Steiner trees. Zbl 1148.68038
Fuchs, B.; Kern, W.; Molle, D.; Richter, S.; Rossmanith, P.; Wang, X. |
|
2007
|
The hub number of Sierpiński-like graphs. Zbl 1234.05178
Lin, Chien-Hung; Liu, Jia-Jie; Wang, Yue-Li; Yen, William Chung-Kung |
|
2011
|
From a zoo to a zoology: Towards a general theory of graph polynomials. Zbl 1162.68502
Makowsky, J. A. |
|
2008
|
Quotient complexity of closed languages. Zbl 1380.68249
Brzozowski, Janusz; Jirásková, Galina; Zou, Chenglong |
|
2014
|
Randomness on computable probability spaces – a dynamical point of view. Zbl 1238.68069
Gács, Peter; Hoyrup, Mathieu; Rojas, Cristóbal |
|
2011
|
Efficient exact algorithms through enumerating maximal independent sets and other techniques. Zbl 1148.68054
Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath |
|
2007
|
Stackelberg strategies for atomic congestion games. Zbl 1203.91035
Fotakis, Dimitris |
|
2010
|
Simple and improved parameterized algorithms for multiterminal cuts. Zbl 1213.68472
Xiao, Mingyu |
|
2010
|
Regular languages and Stone duality. Zbl 0870.68092
Pippenger, N. |
|
1997
|
Sofic tree-shifts. Zbl 1293.68195
Aubrun, Nathalie; Béal, Marie-Pierre |
|
2013
|
How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model. Zbl 1281.68049
Cai, Shukai; Izumi, Taisuke; Wada, Koichi |
|
2012
|
On approximate jumbled pattern matching in strings. Zbl 1253.68372
Burcsi, Péter; Cicalese, Ferdinando; Fici, Gabriele; Lipták, Zsuzsanna |
|
2012
|
Vertex cover problem parameterized above and below tight bounds. Zbl 1209.68276
Gutin, Gregory; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia |
|
2011
|
The behavior of clique-width under graph operations and graph transformations. Zbl 1358.05239
Gurski, Frank |
|
2017
|
A note on exact algorithms for vertex ordering problems on graphs. Zbl 1253.68164
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. |
|
2012
|
Distributed streams algorithms for sliding windows. Zbl 1093.68143
Gibbons, Phillip B.; Tirthapura, Srikanta |
|
2004
|
Real hypercomputation and continuity. Zbl 1122.03039
Ziegler, Martin |
|
2007
|
Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Zbl 1380.68257
Martyugin, Pavel |
|
2014
|
Descendants of primitive substitutions. Zbl 0916.68086
Holton, C.; Zamboni, L. Q. |
|
1999
|
Weak MSO with the unbounding quantifier. Zbl 1227.03051
Bojańczyk, Mikołaj |
|
2011
|
Solving the 2-disjoint paths problem in nearly linear time. Zbl 1103.68100
Tholey, Torsten |
|
2006
|
Efficient update strategies for geometric computing with uncertainty. Zbl 1084.68131
Bruce, Richard; Hoffmann, Michael; Krizanc, Danny; Raman, Rajeev |
|
2005
|
The price of anarchy in network creation games is (mostly) constant. Zbl 1293.91031
Mihalák, Matúš; Schlegel, Jan Christoph |
|
2013
|
DNA computing based on splicing: The existence of universal computers. Zbl 0914.68072
Freund, R.; Kari, L.; Păun, Gh. |
|
1999
|
Characterizing the existence of potential functions in weighted congestion games. Zbl 1278.91013
Harks, Tobias; Klimm, Max; Möhring, Rolf H. |
|
2011
|
The rank-width of edge-coloured graphs. Zbl 1269.05036
Kanté, Mamadou Moustapha; Rao, Michael |
|
2013
|
Rendezvous and election of mobile agents: Impact of sense of direction. Zbl 1107.68022
Barriere, Lali; Flocchini, Paola; Fraigniaud, Pierre; Santoro, Nicola |
|
2007
|
Thread scheduling for multiprogrammed multiprocessors. Zbl 0978.68020
Arora, N. S.; Blumofe, R. D.; Plaxton, C. G. |
|
2001
|
Gaming is a hard job, but someone has to do it! Zbl 1303.68075
Viglietta, Giovanni |
|
2014
|
Robust polynomials and quantum algorithms. Zbl 1121.68049
Buhrman, Harry; Newman, Ilan; Rohrig, Hein; de Wolf, Ronald |
|
2007
|
A Kleene theorem for weighted tree automata. Zbl 1061.68092
Droste, Manfred; Pech, Christian; Vogler, Heiko |
|
2005
|
The bell is ringing in speed-scaled multiprocessor scheduling. Zbl 1310.68048
Greiner, Gero; Nonner, Tim; Souza, Alexander |
|
2014
|
Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications. Zbl 1175.90366
Tsaggouris, George; Zaroliagis, Christos |
|
2009
|
Planar and grid graph reachability problems. Zbl 1183.68409
Allender, Eric; Mix Barrington, David A.; Chakraborty, Tanmoy; Datta, Samir; Roy, Sambuddha |
|
2009
|
The hardness of approximating spanner problems. Zbl 1148.68024
Elkin, Michael; Peleg, David |
|
2007
|
On the uniform computational content of computability theory. Zbl 1420.03110
Brattka, Vasco; Hendtlass, Matthew; Kreuzer, Alexander P. |
|
2017
|
Greedy numeration systems and regularity. Zbl 0895.68088
Hollander, Michael Israel |
|
1998
|
Symbolic dynamics: entropy = dimension = complexity. Zbl 1355.37023
Simpson, Stephen G. |
|
2015
|
Local approximability of max-min and min-max linear programs. Zbl 1253.68360
Floréen, Patrik; Hassinen, Marja; Kaasinen, Joel; Kaski, Petteri; Musto, Topi; Suomela, Jukka |
|
2011
|
Complexity of equations over sets of natural numbers. Zbl 1209.68263
Jeż, Artur; Okhotin, Alexander |
|
2011
|
Weighted logics for unranked tree automata. Zbl 1226.03048
Droste, Manfred; Vogler, Heiko |
|
2011
|
Weighted picture automata and weighted logics. Zbl 1229.03035
Fichtner, Ina |
|
2011
|
Fixed-parameter enumerability of cluster editing and related problems. Zbl 1209.68360
Damaschke, Peter |
|
2010
|
Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs. Zbl 1170.90461
Athanassopoulos, Stavros; Caragiannis, Ioannis; Kaklamanis, Christos |
|
2009
|
Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults. Zbl 1187.68344
Hsieh, Sun-Yuan; Weng, Yu-Fen |
|
2009
|
Selfish routing with incomplete information. Zbl 1151.91331
Gairing, Martin; Monien, Burkhard; Tiemann, Karsten |
|
2008
|
Cross-correlation analysis of cryptographically useful boolean functions and s-boxes. Zbl 0993.68032
Sarkar, P.; Maitra, S. |
|
2002
|
Hamiltonicity of the hierarchical cubic network. Zbl 0993.68003
Fu, Jung-Sheng; Chen, Gen-Huey |
|
2002
|
Solving vertex cover in polynomial time on hyperbolic random graphs. Zbl 1512.05356
Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian |
|
2023
|
Decidability and periodicity of low complexity tilings. Zbl 07680321
Kari, Jarkko; Moutot, Etienne |
|
2023
|
Polynomially ambiguous unary weighted automata over fields. Zbl 07681310
Kostolányi, Peter |
|
2023
|
An automaton group with PSPACE-complete word problem. Zbl 07680323
Wächter, Jan Philipp; Weiß, Armin |
|
2023
|
The space complexity of sum labelling. Zbl 1533.05233
Fernau, Henning; Gajjar, Kshitij |
|
2023
|
Subclasses of Ptime interpreted by programming languages. Zbl 07719393
Bhaskar, Siddharth; Kop, Cynthia; Simonsen, Jakob Grue |
|
2023
|
Synchronous Boolean finite dynamical systems on directed graphs over XOR functions. Zbl 07719398
Ogihara, M.; Uchizawa, K. |
|
2023
|
Random access in persistent strings and segment selection. Zbl 07729114
Bille, Philip; Gørtz, Inge Li |
|
2023
|
Dynamic multiple-message broadcast: bounding throughput in the affectance model. Zbl 07729119
Kowalski, Dariusz R.; Mosteiro, Miguel A.; Zaki, Kevin |
|
2023
|
FKT is not universal – a planar Holant dichotomy for symmetric constraints. Zbl 1534.68075
Cai, Jin-Yi; Fu, Zhiguo; Guo, Heng; Williams, Tyson |
|
2022
|
Multistage vertex cover. Zbl 07523542
Fluschnik, Till; Niedermeier, Rolf; Rohm, Valentin; Zschoche, Philipp |
|
2022
|
An improved deterministic parameterized algorithm for cactus vertex deletion. Zbl 1487.05250
Aoike, Yuuki; Gima, Tatsuya; Hanaka, Tesshu; Kiyomi, Masashi; Kobayashi, Yasuaki; Kobayashi, Yusuke; Kurita, Kazuhiro; Otachi, Yota |
|
2022
|
On the computational complexity of decision problems about multi-player Nash equilibria. Zbl 1493.91005
Berthelsen, Marie Louisa Tølbøll; Hansen, Kristoffer Arnsfelt |
|
2022
|
Stable multi-level monotonic eroders. Zbl 1536.37019
Gács, Péter; Törmä, Ilkka |
|
2022
|
On the existence of three-dimensional stable matchings with cyclic preferences. Zbl 1493.91093
Lam, Chi-Kit; Plaxton, C. Gregory |
|
2022
|
Impartial selection with additive approximation guarantees. Zbl 1493.91029
Caragiannis, Ioannis; Christodoulou, George; Protopapas, Nicos |
|
2022
|
The power of the weighted sum scalarization for approximating multiobjective optimization problems. Zbl 1485.90121
Bazgan, Cristina; Ruzika, Stefan; Thielen, Clemens; Vanderpooten, Daniel |
|
2022
|
Target set selection parameterized by vertex cover and more. Zbl 1524.90325
Banerjee, Suman; Mathew, Rogers; Panolan, Fahad |
|
2022
|
The declining price anomaly is not universal in multi-buyer sequential auctions (but almost is). Zbl 1493.91058
Narayan, Vishnu V.; Prebet, Enguerrand; Vetta, Adrian |
|
2022
|
Maximum stable matching with one-sided ties of bounded length. Zbl 1489.68401
Lam, Chi-Kit; Plaxton, C. Gregory |
|
2022
|
Non-existence of stable social groups in information-driven networks. Zbl 1495.91088
Chaintreau, Augustin; Ducoffe, Guillaume; Mazauric, Dorian |
|
2022
|
Multi-pass streaming algorithms for monotone submodular function maximization. Zbl 1533.68414
Huang, Chien-Chung; Kakimura, Naonori |
|
2022
|
Faster parameterized algorithm for cluster vertex deletion. Zbl 1517.68308
Tsur, Dekel |
|
2021
|
Token sliding on split graphs. Zbl 1517.68273
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian |
|
2021
|
Computability of products of chainable continua. Zbl 1535.03228
Čelar, Matea; Iljazović, Zvonko |
|
2021
|
Finite sequentiality of unambiguous max-plus tree automata. Zbl 1517.68211
Paul, Erik |
|
2021
|
Approximation results for makespan minimization with budgeted uncertainty. Zbl 1478.90036
Bougeret, Marin; Jansen, Klaus; Poss, Michael; Rohwedder, Lars |
|
2021
|
Fast scheduling in distributed transactional memory. Zbl 1464.68036
Busch, Costas; Herlihy, Maurice; Popovic, Miroslav; Sharma, Gokarna |
|
2021
|
The price of fairness for indivisible goods. Zbl 1471.91196
Bei, Xiaohui; Lu, Xinhang; Manurangsi, Pasin; Suksompong, Warut |
|
2021
|
On triangle estimation using tripartite independent set queries. Zbl 1508.68259
Bhattacharya, Anup; Bishnu, Arijit; Ghosh, Arijit; Mishra, Gopinath |
|
2021
|
The containment problem for unambiguous register automata and unambiguous timed automata. Zbl 1517.68207
Mottet, Antoine; Quaas, Karin |
|
2021
|
Parameterized complexity of conflict-free set cover. Zbl 1517.68146
Jacob, Ashwin; Majumdar, Diptapriyo; Raman, Venkatesh |
|
2021
|
Unpopularity factor in the marriage and roommates problems. Zbl 1518.91175
Ruangwises, Suthee; Itoh, Toshiya |
|
2021
|
Forward looking Huffman coding. Zbl 1517.68111
Klein, Shmuel T.; Saadia, Shoham; Shapira, Dana |
|
2021
|
On the cycle augmentation problem: hardness and approximation algorithms. Zbl 1473.05292
Gálvez, Waldo; Grandoni, Fabrizio; Jabal Ameli, Afrouz; Sornat, Krzysztof |
|
2021
|
Semi-oblivious chase termination: the sticky case. Zbl 1477.68088
Calautti, Marco; Pieris, Andreas |
|
2021
|
The non-hardness of approximating circuit size. Zbl 1522.68194
Allender, Eric; Ilango, Rahul; Vafa, Neekon |
|
2021
|
Streaming algorithms for bin packing and vector scheduling. Zbl 1528.68408
Cormode, Graham; Veselý, Pavel |
|
2021
|
Restart strategies in a continuous setting. Zbl 1508.68413
Lorenz, Jan-Hendrik |
|
2021
|
A parameterized complexity view on collapsing \(k\)-cores. Zbl 1508.68269
Luo, Junjie; Molter, Hendrik; Suchý, Ondřej |
|
2021
|
First-order orbit queries. Zbl 1518.37014
Almagor, Shaull; Ouaknine, Joël; Worrell, James |
|
2021
|
Index-based, high-dimensional, cosine threshold querying with optimality guarantees. Zbl 1517.68101
Li, Yuliang; Wang, Jianguo; Pullman, Benjamin; Bandeira, Nuno; Papakonstantinou, Yannis |
|
2021
|
Consistent query answering for primary keys in Datalog. Zbl 1477.68091
Koutris, Paraschos; Wijsen, Jef |
|
2021
|
On the expressive power of linear algebra on graphs. Zbl 1466.05118
Geerts, Floris |
|
2021
|
Exploration of dynamic cactuses with sub-logarithmic overhead. Zbl 1519.68192
Ilcinkas, David; Wade, Ahmed M. |
|
2021
|
On the relation between structured \(d\)-DNNFs and SDDs. Zbl 1522.68536
Bollig, Beate; Farenholtz, Martin |
|
2021
|
Stable divisorial gonality is in NP. Zbl 1477.68204
Bodlaender, Hans L.; van der Wegen, Marieke; van der Zanden, Tom C. |
|
2021
|
On decidability of theories of regular languages. Zbl 1517.68185
Dudakov, Sergey; Karlov, Boris |
|
2021
|
Transition property for cube-free words. Zbl 1517.68322
Petrova, Elena A.; Shur, Arseny M. |
|
2021
|
On Tseitin formulas, read-once branching programs and treewidth. Zbl 1517.68092
Glinskih, Ludmila; Itsykson, Dmitry |
|
2021
|
The minimum tollbooth problem in atomic network congestion games with unsplittable flows. Zbl 1471.91020
Nickerl, Julian |
|
2021
|
Reachability problems on reliable and lossy queue automata. Zbl 1503.68174
Köcher, Chris |
|
2021
|
Constructing antidictionaries of long texts in output-sensitive space. Zbl 1517.68428
Ayad, Lorraine A. K.; Badkobeh, Golnaz; Fici, Gabriele; Héliou, Alice; Pissis, Solon P. |
|
2021
|
Additive number theory via automata theory. Zbl 1475.11040
Rajasekaran, Aayush; Shallit, Jeffrey; Smith, Tim |
|
2020
|
Complexity and inapproximability results for parallel task scheduling and strip packing. Zbl 1477.68119
Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars |
|
2020
|
On the tree conjecture for the network creation game. Zbl 1443.91071
Bilò, Davide; Lenzner, Pascal |
|
2020
|
Optimal dislocation with persistent errors in subquadratic time. Zbl 1433.68111
Geissmann, Barbara; Leucci, Stefano; Liu, Chih-Hung; Penna, Paolo |
|
2020
|
Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings. Zbl 1503.68317
Watanabe, Kiichi; Nakashima, Yuto; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki |
|
2020
|
Conflict free version of covering problems on graphs: classical and parameterized. Zbl 1453.68136
Jain, Pallavi; Kanesh, Lawqueen; Misra, Pranabendu |
|
2020
|
On the parameterized complexity of graph modification to first-order logic properties. Zbl 1434.68208
Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M. |
|
2020
|
Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits. Zbl 1433.68177
Bannach, Max; Tantau, Till |
|
2020
|
Parameterized complexity of min-power asymmetric connectivity. Zbl 1503.68080
Bentert, Matthias; Haag, Roman; Hofer, Christian; Koana, Tomohiro; Nichterlein, André |
|
2020
|
An improved FPT algorithm for independent feedback vertex set. Zbl 1507.68231
Li, Shaohua; Pilipczuk, Marcin |
|
2020
|
Lower bound techniques for QBF expansion. Zbl 1471.03081
Beyersdorff, Olaf; Blinkhorn, Joshua |
|
2020
|
Dependences in strategy logic. Zbl 1484.68100
Gardy, Patrick; Bouyer, Patricia; Markey, Nicolas |
|
2020
|
Multiplication algorithm based on Collatz function. Zbl 1462.11112
Barina, David |
|
2020
|
Dichotomy for Holant\(^\ast\) problems on the Boolean domain. Zbl 1503.68199
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji |
|
2020
|
On approximating the stationary distribution of time-reversible Markov chains. Zbl 1436.60035
Bressan, Marco; Peserico, Enoch; Pretto, Luca |
|
2020
|
Deterministic min-cost matching with delays. Zbl 1444.68297
Azar, Yossi; Jacob Fanani, Amit |
|
2020
|
On the stab number of rectangle intersection graphs. Zbl 1442.05187
Chakraborty, Dibyayan; Francis, Mathew C. |
|
2020
|
On limitations of structured (deterministic) DNNFs. Zbl 1446.68152
Bollig, Beate; Buttkus, Matthias |
|
2020
|
Enumeration complexity of conjunctive queries with functional dependencies. Zbl 1446.68052
Carmeli, Nofar; Kröll, Markus |
|
2020
|
Connecting knowledge compilation classes and width parameters.
(Connecting knowledge compilation classes width parameters.) Zbl 1446.68149
Amarilli, Antoine; Capelli, Florent; Monet, Mikaël; Senellart, Pierre |
|
2020
|
Complexity of fall coloring for restricted graph classes. Zbl 1507.68230
Lauri, Juho; Mitillos, Christodoulos |
|
2020
|
Complexity and algorithms for semipaired domination in graphs. Zbl 1503.68223
Henning, Michael A.; Pandey, Arti; Tripathi, Vikash |
|
2020
|
On envy-free revenue approximation for combinatorial buyers with budgets. Zbl 1466.91121
Markakis, Evangelos; Ntokos, Apostolos; Telelis, Orestis |
|
2020
|
Effective categoricity of automatic equivalence and nested equivalence structures. Zbl 1485.03109
Carson, Jacob; Cenzer, Douglas; Remmel, Jeffrey B. |
|
2020
|
Santha-Vazirani sources, deterministic condensers and very strong extractors. Zbl 1476.68081
Gavinsky, Dmitry; Pudlák, Pavel |
|
2020
|
Recognizing read-once functions from depth-three formulas. Zbl 1434.68201
Kozachinskiy, Alexander |
|
2020
|
Slopes of multidimensional subshifts. Zbl 1440.37025
Jeandel, Emmanuel; Moutot, Etienne; Vanier, Pascal |
|
2020
|
Fixed-parameter tractable algorithm and polynomial kernel for Max-Cut Above Spanning Tree. Zbl 1434.68748
Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav |
|
2020
|
New bounds for truthful scheduling on two unrelated selfish machines. Zbl 1434.68678
Kuryatnikova, Olga; Vera, Juan C. |
|
2020
|
Algorithm for online 3-path vertex cover. Zbl 1434.68696
Zhang, Yubai; Zhang, Zhao; Shi, Yishuo; Li, Xianyue |
|
2020
|
Space-efficient algorithms for longest increasing subsequence. Zbl 1433.68632
Kiyomi, Masashi; Ono, Hirotaka; Otachi, Yota; Schweitzer, Pascal; Tarui, Jun |
|
2020
|
Advice complexity of priority algorithms. Zbl 1444.68299
Borodin, Allan; Boyar, Joan; Larsen, Kim S.; Pankratov, Denis |
|
2020
|
Distribution policies for Datalog. Zbl 1446.68057
Ketsman, Bas; Albarghouthi, Aws; Koutris, Paraschos |
|
2020
|
Generic results for concatenation hierarchies. Zbl 1423.68264
Place, Thomas; Zeitoun, Marc |
|
2019
|
Verification of quantum computation: an overview of existing approaches. Zbl 1423.68281
Gheorghiu, Alexandru; Kapourniotis, Theodoros; Kashefi, Elham |
|
2019
|
A logic for document spanners. Zbl 1430.68081
Freydenberger, Dominik D. |
|
2019
|
Lower bounds for several online variants of bin packing. Zbl 1436.68402
Balogh, János; Békési, József; Dósa, György; Epstein, Leah; Levin, Asaf |
|
2019
|
On the parameterized complexity of contraction to generalization of trees. Zbl 1435.68119
Agarwal, Akanksha; Saurabh, Saket; Tale, Prafullkumar |
|
2019
|
On the relative succinctness of sentential decision diagrams. Zbl 1435.68320
Bollig, Beate; Buttkus, Matthias |
|
2019
|
Comparing linear width parameters for directed graphs. Zbl 1420.05068
Gurski, Frank; Rehs, Carolin |
|
2019
|
The real computational complexity of minmax value and equilibrium refinements in multi-player games. Zbl 1422.91046
Hansen, Kristoffer Arnsfelt |
|
2019
|
Logarithmic query complexity for approximate Nash computation in large games. Zbl 1411.91052
Goldberg, Paul W.; Marmolejo-Cossío, Francisco J.; Wu, Zhiwei Steven |
|
2019
|
The operator approach to entropy games. Zbl 1422.91080
Akian, Marianne; Gaubert, Stéphane; Grand-Clément, Julien; Guillaud, Jérémie |
|
2019
|
Better streaming algorithms for the maximum coverage problem. Zbl 1421.90128
McGregor, Andrew; Vu, Hoa T. |
|
2019
|
Synchronous gathering without multiplicity detection: a certified algorithm. Zbl 1423.68522
Balabonski, Thibaut; Delga, Amélie; Rieg, Lionel; Tixeuil, Sébastien; Urbain, Xavier |
|
2019
|
Pattern matching and consensus problems on weighted sequences and profiles. Zbl 1423.68620
Kociumaka, Tomasz; Pissis, Solon P.; Radoszewski, Jakub |
|
2019
|
The descriptive complexity of subgraph isomorphism without numerics. Zbl 1435.68114
Verbitsky, Oleg; Zhukovskii, Maksim |
|
2019
|
| ...and 967 more Documents |
