Výsledky vyhledávání - "Parametrized complexity"

Akademický článek

Breaking intractability of spanning caterpillar tree problem: A logical approach

Autor: Masoud Khosravani

Publikováno v: AUT Journal of Mathematics and Computing, Vol 3, Iss 2, Pp 147-151 (2022)

In this paper we pursue a logical approach to prove that the optimisation problem of finding a spanning caterpillar tree in a graph has polynomial algorithm for bounded tree width graphs. A caterpillar (tree) is a tree with the property that if one r

Externí odkaz: https://doaj.org/article/e62573ba11f8470eab707ea8a4e7b590

Zobrazit plný text záznamu

Akademický článek

Parameterized Complexity on a New Sorting Algorithm: A Study in Simulation

Autor: KUMAR Prashant, KUMARI Anchala, CHAKRABORTY Soubhik

Publikováno v: Anale: Seria Informatică, Vol VII, Iss 2, Pp 9-22 (2009)

Sundararajan and Chakraborty (2007) introduced a new sorting algorithm by modifying the fast and popular Quick sort and removing the interchanges. In a subsequent empirical study, Sourabh, Sundararajan and Chakraborty (2007) demonstrated that this al

Externí odkaz: https://doaj.org/article/7ff2c69bbda64cc78b7750e750a498b3

Zobrazit plný text záznamu

Akademický článek

How many interchanges does the selection sort make for iid geometric(p) input?

Autor: SAHANI Debasish, CHAKRABORTY Soubhik

Publikováno v: Anale: Seria Informatică, Vol VII, Iss 2, Pp 67-76 (2009)

The note derives an expression for the number of interchanges made by selection sort when the sorting elements are iid variates from geometric distribution. Empirical results reveal we can work with a simpler model compared to what is suggestive in t

Externí odkaz: https://doaj.org/article/fd6c50aebea24c1596358a36d1e13874

Zobrazit plný text záznamu

The Parametrized Complexity of Quantum Verification

Autor: Arunachalam, Srinivasan, Bravyi, Sergey, Nirkhe, Chinmay, O'Gorman, Bryan

We initiate the study of parameterized complexity of QMA problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorith

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1ce5bd3f71bc82ffc23d797e395ae9f4

Zobrazit plný text záznamu

Akademický článek

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

A Generic Strategy Improvement Method for Simple Stochastic Games

Autor: Auger, David, Montjoye, Xavier Badin De, Strozecki, Yann

Publikováno v: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Aug 2021, Tallinn, Estonia. ⟨10.4230/LIPIcs.MFCS.2021.12⟩

We present a generic strategy improvement algorithm (GSIA) to find an optimal strategy of simple stochastic games (SSG). We prove the correctness of GSIA, and derive a general complexity bound, which implies and improves on the results of several art

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cd2e62523290b0682e077e5aa2d91bc0
https://hal.archives-ouvertes.fr/hal-03401817

Zobrazit plný text záznamu

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem

Autor: Hengeveld, Simon, Miltzow, Till, Sub Geometric Computing, Geometric Computing

Publikováno v: 37th International Symposium on Computational Geometry, 1
STARTPAGE=1;TITLE=37th International Symposium on Computational Geometry

Given a closed simple polygon P, we say two points p,q see each other if the segment seg(p,q) is fully contained in P. The art gallery problem seeks a minimum size set G ⊂ P of guards that sees P completely. The only currently correct algorithm to

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3e4397332c0bfa986cdcf9d3cd6a038f
https://doi.org/10.4230/lipics.socg.2021.44

Zobrazit plný text záznamu

Akademický článek

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Avoiding crossings in non-planar graph layouts

Autor: Klute, Fabian

Reducing crossings in node-link diagrams of networks is a topic of great interest in graph drawing and information visualization. When viewed from the perspective of graph drawing this problem is often studied via considering the underlying graph wit

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::c3eeac68066b2f2dd1263f07c3449cb4

Zobrazit plný text záznamu

Parameterized Complexity of Independent Set in H-Free Graphs

Autor: Édouard Bonnet, Pierre Charbit, Rémi Watrigant, Nicolas Bousquet, Stéphan Thomassé

Publikováno v: IPEC 2018-13th International Symposium on Parameterized and Exact Computation
IPEC 2018-13th International Symposium on Parameterized and Exact Computation, Aug 2018, Helsinki, Finland. ⟨10.4230/LIPIcs.CVIT.2016.23⟩
Algorithmica
Algorithmica, Springer Verlag, 2020, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Algorithmica, Springer Verlag, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Algorithmica, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩

In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of $H$-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains $NP$-hard for most graphs $H$, we study its

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f6a60a7ad730e8b4bd467d2fb9aae78c
http://arxiv.org/abs/1810.04620

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání