„complexity dichotomy“

Suchergebnisse

1.000+ Treffer

• Graph Isomorphism for $$(H_1,H_2)$$ ( H 1 , H 2 ) -Free Graphs: An Almost Complete Dichotomy
  Bonamy, Marthe ; Bousquet, Nicolas ; Dabrowski, Konrad K. ; Johnson, Matthew ; Paulusma, Daniel ; Pierron, Théo
• Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs
  Brunner, Josh ; Demaine, Erik D. ; Diomidova, Jenny ; Gomez, Timothy ; Hecher, Markus ; Stock, Frederick ; Zhou, Zixiang 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Binary Matrix Completion Under Diameter Constraints
  Koana, Tomohiro ; Froese, Vincent ; Niedermeier, Rolf 2021 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Temporal Valued Constraint Satisfaction Problems
  Bodirsky, Manuel ; Bonnet, Édouard ; Semanišinová, Žaneta 2025 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• A Topological Version of Schaefer’s Dichotomy Theorem
  Schnider, Patrick ; Weber, Simon 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Towards a Complexity-Theoretic Dichotomy for TQFT Invariants
  Bridges, Nicolas ; Samperton, Eric 2025 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• From an Odd Arity Signature to a Holant Dichotomy
  Meng, Boning ; Wang, Juqiu ; Xia, Mingji ; Zheng, Jiayi 2025 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Holant* Dichotomy on Domain Size 3: A Geometric Perspective
  Cai, Jin-Yi ; Ihm, Jin Soo 2025 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• P-Time Algorithms for Typical #EO Problems
  Meng, Boning ; Wang, Juqiu ; Xia, Mingji 2025 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Parameterized Complexity Dichotomy for Steiner Multicut
  Bringmann, Karl ; Hermelin, Danny ; Mnich, Matthias ; van Leeuwen, Erik Jan 2015 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• A Complexity Dichotomy for Partition Functions with Mixed Signs
  Goldberg, Leslie Ann ; Grohe, Martin ; Jerrum, Mark ; Thurley, Marc 2009 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
  Feldmann, Andreas Emil ; Marx, Dániel 2016 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs
  Le, Hoang-Oanh ; Le, Van Bang 2022 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
  Paul-Pena, Daniel ; Seshadhri, C. 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs
  Lozin, Vadim ; Martin, Barnaby ; Pandey, Sukanya ; Paulusma, Daniel ; Siggers, Mark ; Smith, Siani ; van Leeuwen, Erik Jan 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper)
  de Vlas, Jorke M. 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations
  Bougeret, Marin ; Jansen, Bart M. P. ; Sau, Ignasi 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs
  Johnson, Matthew ; Martin, Barnaby ; Pandey, Sukanya ; Paulusma, Daniel ; Smith, Siani ; van Leeuwen, Erik Jan 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• 09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability
  Bulatov, Andrei A. ; Grohe, Martin ; Kolaitis, Phokion G. ; Krokhin, Andrei
• 09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability
  Bulatov, Andrei A. ; Grohe, Martin ; Kolaitis, Phokion G. ; Krokhin, Andrei