8 Search Results for "Teruyama, Junichi"

Document
DOI: 10.4230/LIPIcs.FUN.2026.40
An ASP-Completeness Framework for Dynasty Puzzles

Authors: Kosuke Susukita

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
A certain class of pencil-and-paper puzzles shares common rules: given a grid, certain cells must be shaded such that i) no two shaded cells are orthogonally adjacent, and ii) all unshaded cells are orthogonally connected. Such puzzles are sometimes referred to as "dynasty puzzles" within parts of the online puzzle community. We introduce a framework for proving the ASP-completeness (i.e., NP-complete under parsimonious reductions) of various dynasty puzzles. We apply this framework to seven specific dynasty puzzles - Akichiwake, Aquapelago, Ayeheya, Guide Arrow, Heyawake, Hitori, and Kurodoko. As a consequence, for given k solutions of any of these puzzles, deciding whether a distinct solution exists is NP-complete, and counting the number of solutions is #P-complete. Our results strengthen the known result of ASP-completeness for Heyawake and establish the ASP-completeness of the other six puzzles. The main idea is to reconstruct the reduction from the Tree-Residue Vertex-Breaking Problem (TRVB) to the Hamiltonian Cycle Problem introduced by MIT Hardness Group (2024). In our framework, the connectivity of the unshaded cells ensures the connectivity of the shaded cells, allowing the shaded cells to simulate TRVB, which is also an alternative representation of the Hamiltonian cycles under certain conditions.
Cite as

Kosuke Susukita. An ASP-Completeness Framework for Dynasty Puzzles. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{susukita:LIPIcs.FUN.2026.40,
  author =	{Susukita, Kosuke},
  title =	{{An ASP-Completeness Framework for Dynasty Puzzles}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{40:1--40:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.40},
  URN =		{urn:nbn:de:0030-drops-257596},
  doi =		{10.4230/LIPIcs.FUN.2026.40},
  annote =	{Keywords: ASP-completeness, pencil-and-paper puzzles, dynasty puzzles, Hitori, Kurodoko, Hamiltonian cycle, Tree-Residue Vertex-Breaking}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.25
Exact Algorithms and Hardness Result for the Boolean Connectivity Problem of k-Horn Formulas

Authors: Takashi Horiyama, Yuto Okura, Kazuhisa Seto, and Junichi Teruyama

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the n-dimensional hypercube. This problem is known to be coNP-complete, even when restricted to k-Horn formulas for k ≥ 3, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the complexity of the Boolean connectivity problem for k-Horn formulas, referred to as Conn k-Horn. We first present an exact exponential-time algorithm for Conn k-Horn without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in O^*(2^{(1-1/2k)n}) time, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of k-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We then examine both algorithmic and hardness results for Conn 3-Horn under bounded variable occurrences. On the algorithmic side, we propose a polynomial-time algorithm for Conn 3-Horn when each clause contains exactly three literals and each variable appears at most three times. This result generalizes to Conn k-Horn under the same structural constraints, in which each clause contains exactly k literals and each variable appears at most k times. On the hardness side, we prove that Conn 3-Horn remains coNP-complete even when restricted to instances in which each variable appears exactly four times.
Cite as

Takashi Horiyama, Yuto Okura, Kazuhisa Seto, and Junichi Teruyama. Exact Algorithms and Hardness Result for the Boolean Connectivity Problem of k-Horn Formulas. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{horiyama_et_al:LIPIcs.IPEC.2025.25,
  author =	{Horiyama, Takashi and Okura, Yuto and Seto, Kazuhisa and Teruyama, Junichi},
  title =	{{Exact Algorithms and Hardness Result for the Boolean Connectivity Problem of k-Horn Formulas}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.25},
  URN =		{urn:nbn:de:0030-drops-251577},
  doi =		{10.4230/LIPIcs.IPEC.2025.25},
  annote =	{Keywords: k-Horn, Boolean connectivity, bounded variable occurrence, hardness, exact algorithm, satisfiability}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.39
Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules

Authors: Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, and Xiao Zhou

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In reconfiguration problems, we are given two feasible solutions to a graph problem and asked whether one can be transformed into the other via a sequence of feasible intermediate solutions under a given reconfiguration rule. While earlier work focused on modifying a single element at a time, recent studies have started examining how different rules impact computational complexity. Motivated by recent progress, we study Independent Set Reconfiguration (ISR) and Vertex Cover Reconfiguration (VCR) under the k-Token Jumping (k-TJ) and k-Token Sliding (k-TS) models. In k-TJ, up to k vertices may be replaced, while k-TS additionally requires a perfect matching between removed and added vertices. It is known that the complexity of ISR crucially depends on k, ranging from PSPACE-complete and NP-complete to polynomial-time solvable. In this paper, we further explore the gradient of computational complexity of the problems. We first show that ISR under k-TJ with k = |I| - μ remains NP-hard when μ is any fixed positive integer and the input graph is restricted to graphs of maximum degree 3 or planar graphs of maximum degree 4, where |I| is the size of feasible solutions. In addition, we prove that the problem belongs to NP not only for μ = O(1) but also for μ = O(log |I|). In contrast, we show that VCR under k-TJ is in XP when parameterized by μ = |S| - k, where |S| is the size of feasible solutions. Furthermore, we establish the PSPACE-completeness of ISR and VCR under both k-TJ and k-TS on several graph classes, for fixed k as well as superconstant k relative to the size of feasible solutions.
Cite as

Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, and Xiao Zhou. Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ISAAC.2025.39,
  author =	{Hirahara, Shuichi and Ohsaka, Naoto and Suga, Tatsuhiro and Suzuki, Akira and Tamura, Yuma and Zhou, Xiao},
  title =	{{Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{39:1--39:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.39},
  URN =		{urn:nbn:de:0030-drops-249474},
  doi =		{10.4230/LIPIcs.ISAAC.2025.39},
  annote =	{Keywords: combinatorial reconfiguration, extended reconfiguration rule, independent set reconfiguration, vertex cover reconfiguration, PSPACE-completeness, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.67
#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank

Authors: Nutan Limaye, Adarsh Srinivasan, and Srikanth Srinivasan

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
There is a large body of work that shows how to leverage lower bound techniques for circuit classes to obtain satisfiability algorithms that run in better than brute-force time [Ramamohan Paturi et al., 1997; Ryan Williams, 2014]. For circuits with threshold gates, there are several such algorithms based on either - Probabilistic Representations by low-degree polynomials, which allow for the use of fast polynomial evaluation algorithms, or - Low rank, which allows for an efficient reduction to rectangular matrix multiplication. In this paper, we use a related notion of probabilistic rank to obtain satisfiability algorithms for circuit classes contained in ACC⁰∘3-PTF, i.e. constant-depth circuits with modular counting gates and a single layer of degree-3 polynomial threshold functions. Even for the special case of a single 3-PTF, it is not clear how to use either of the above two strategies to get a non-trivial satisfiability algorithm. The best known algorithm in this case previously was based on memoization and yields worse guarantees than our algorithm.
Cite as

Nutan Limaye, Adarsh Srinivasan, and Srikanth Srinivasan. #SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 67:1-67:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{limaye_et_al:LIPIcs.MFCS.2025.67,
  author =	{Limaye, Nutan and Srinivasan, Adarsh and Srinivasan, Srikanth},
  title =	{{#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{67:1--67:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.67},
  URN =		{urn:nbn:de:0030-drops-241744},
  doi =		{10.4230/LIPIcs.MFCS.2025.67},
  annote =	{Keywords: probabilistic polynomials, probabilistic rank, circuit satisfiability, circuit lower bounds, polynomial method, threshold circuits}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2021.13
Locating Evacuation Centers Optimally in Path and Cycle Networks

Authors: Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).
Cite as

Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama. Locating Evacuation Centers Optimally in Path and Cycle Networks. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{benkoczi_et_al:OASIcs.ATMOS.2021.13,
  author =	{Benkoczi, Robert and Bhattacharya, Binay and Higashikawa, Yuya and Kameda, Tsunehiko and Katoh, Naoki and Teruyama, Junichi},
  title =	{{Locating Evacuation Centers Optimally in Path and Cycle Networks}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{13:1--13:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.13},
  URN =		{urn:nbn:de:0030-drops-148825},
  doi =		{10.4230/OASIcs.ATMOS.2021.13},
  annote =	{Keywords: Efficient algorithms, facility location, minmax sink, evacuation problem, dynamic flow in network}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.58
Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

Authors: Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
The satisfiability of a given branching program is to determine whether there exists a consistent path from the root to 1-sink. In a syntactic read-k-times branching program, each variable appears at most k times in any path from the root to a sink. We provide a satisfiability algorithm for syntactic read-k-times branching programs with n variables and m edges that runs in time O\left(\poly(n, m^{k^2})\cdot 2^{(1-\mu(k))n}\right), where \mu(k) = \frac{1}{4^{k+1}}. Our algorithm is based on the decomposition technique shown by Borodin, Razborov and Smolensky [Computational Complexity, 1993].
Cite as

Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama. Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 58:1-58:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nagao_et_al:LIPIcs.ISAAC.2017.58,
  author =	{Nagao, Atsuki and Seto, Kazuhisa and Teruyama, Junichi},
  title =	{{Satisfiability Algorithm for Syntactic Read-\$k\$-times Branching Programs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{58:1--58:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.58},
  URN =		{urn:nbn:de:0030-drops-82423},
  doi =		{10.4230/LIPIcs.ISAAC.2017.58},
  annote =	{Keywords: branching program, read-k-times, satisfiability, moderately exponential time, polynomial space}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.82
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

Authors: Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
A Boolean function f:{0,1}^n -> {0,1} is weighted symmetric if there exist a function g: Z -> {0,1} and integers w_0, w_1, ..., w_n such that f(x_1, ...,x_n) = g(w_0+sum_{i=1}^n w_i x_i) holds. In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, OR, NOT gates and a limited number of weighted symmetric gates. Our algorithms run in time super-polynomially faster than 2^n even when the number of gates is super-polynomial and the maximum weight of symmetric gates is nearly exponential. With an additional trick, we give an algorithm for the maximum satisfiability problem that runs in time poly(n^t)*2^{n-n^{1/O(t)}} for instances with n variables, O(n^t) clauses and arbitrary weights. To the best of our knowledge, this is the first moderately exponential time algorithm even for Max 2SAT instances with arbitrary weights. Through the analysis of our algorithms, we obtain average-case lower bounds and compression algorithms for such circuits and worst-case lower bounds for majority votes of such circuits, where all the lower bounds are against the generalized Andreev function. Our average-case lower bounds might be of independent interest in the sense that previous ones for similar circuits with arbitrary symmetric gates rely on communication complexity lower bounds while ours are based on the restriction method.
Cite as

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama. Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 82:1-82:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sakai_et_al:LIPIcs.MFCS.2016.82,
  author =	{Sakai, Takayuki and Seto, Kazuhisa and Tamaki, Suguru and Teruyama, Junichi},
  title =	{{Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{82:1--82:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.82},
  URN =		{urn:nbn:de:0030-drops-64905},
  doi =		{10.4230/LIPIcs.MFCS.2016.82},
  annote =	{Keywords: exponential time algorithm, circuit complexity, circuit minimization, maximum satisfiability}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.90
Improved Exact Algorithms for Mildly Sparse Instances of Max SAT

Authors: Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We present improved exponential time exact algorithms for Max SAT. Our algorithms run in time of the form O(2^{(1-mu(c))n}) for instances with n variables and m=cn clauses. In this setting, there are three incomparable currently best algorithms: a deterministic exponential space algorithm with mu(c)=1/O(c * log(c)) due to Dantsin and Wolpert [SAT 2006], a randomized polynomial space algorithm with mu(c)=1/O(c * log^3(c)) and a deterministic polynomial space algorithm with mu(c)=1/O(c^2 * log^2(c)) due to Sakai, Seto and Tamaki [Theory Comput. Syst., 2015]. Our first result is a deterministic polynomial space algorithm with mu(c)=1/O(c * log(c)) that achieves the previous best time complexity without exponential space or randomization. Furthermore, this algorithm can handle instances with exponentially large weights and hard constraints. The previous algorithms and our deterministic polynomial space algorithm run super-polynomially faster than 2^n only if m=O(n^2). Our second results are deterministic exponential space algorithms for Max SAT with mu(c)=1/O((c * log(c))^{2/3}) and for Max 3-SAT with mu(c)=1/O(c^{1/2}) that run super-polynomially faster than 2^n when m=o(n^{5/2}/log^{5/2}(n)) and m=o(n^3/log^2(n)) respectively.
Cite as

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama. Improved Exact Algorithms for Mildly Sparse Instances of Max SAT. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 90-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{sakai_et_al:LIPIcs.IPEC.2015.90,
  author =	{Sakai, Takayuki and Seto, Kazuhisa and Tamaki, Suguru and Teruyama, Junichi},
  title =	{{Improved Exact Algorithms for Mildly Sparse Instances of Max SAT}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{90--101},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.90},
  URN =		{urn:nbn:de:0030-drops-55747},
  doi =		{10.4230/LIPIcs.IPEC.2015.90},
  annote =	{Keywords: maximum satisfiability, weighted, polynomial space, exponential space}
}
  • Refine by Type
  • 8 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2021
  • 1 2017
  • 1 2016
  • Show More...

  • Refine by Author
  • 5 Teruyama, Junichi
  • 4 Seto, Kazuhisa
  • 2 Sakai, Takayuki
  • 2 Tamaki, Suguru
  • 1 Benkoczi, Robert
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 2 maximum satisfiability
  • 2 polynomial space
  • 2 satisfiability
  • 1 ASP-completeness
  • 1 Boolean connectivity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact