Results 51 to 60 of about 35,538 (168)
Reducing the rank of a matroid [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 We consider the rank reduction problem for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $
Gwenaël Joret, Adrian Vetta
doaj +1 more source
Computing Heegaard Genus is NP-Hard [PDF]
, 2017 Version for publication. To appear in the collection of papers "A Journey through Discrete Mathematics. A Tribute to Jiri Matousek" edited by Martin Loebl, Jaroslav Nesetril and Robin Thomas, to be published by ...
Bachman, David +2 more
openaire +2 more sources
A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem
Algorithms, 2012 A disentanglement puzzle consists of mechanically interlinked pieces, and the puzzle is solved by disentangling one piece from another set of pieces. A string puzzle consists of strings entangled with one or more wooden pieces.
Kenichi Morita +2 more
doaj +1 more source
Haskell-style overloading is NP-hard [PDF]
Proceedings of 1994 IEEE International Conference on Computer Languages (ICCL'94), 2002 Extensions of the ML type system, based on constrained type schemes, have been proposed for languages with overloading. Type inference in these systems requires solving the following satisfiability problem. Given a set of type assumptions C over finite types and a type basis A, is there is a substitution S that satisfies C in that A implies that CS is ...
openaire +2 more sources
Improved lower bound for the complexity of unique shortest vector problem
Cybersecurity, 2023 Unique shortest vector problem (uSVP) plays an important role in lattice based cryptography. Many cryptographic schemes based their security on it. For the cofidence of those applications, it is essential to clarify the complexity of uSVP with different ...
Baolong Jin, Rui Xue
doaj +1 more source
Exploiting bounded signal flow for graph orientation based on cause-effect pairs
Algorithms for Molecular Biology, 2011 Background We consider the following problem: Given an undirected network and a set of sender-receiver pairs, direct all edges such that the maximum number of "signal flows" defined by the pairs can be routed respecting edge directions.
Niedermeier Rolf +4 more
doaj +1 more source
An efficient rank based approach for closest string and closest substring. [PDF]
PLoS ONE, 2012 This paper aims to present a new genetic approach that uses rank distance for solving two known NP-hard problems, and to compare rank distance with other distance measures for strings.
Liviu P Dinu, Radu Ionescu
doaj +1 more source
Symbolic Regression is NP-hard
, 2022 corrected citation Abbass 2002 -> Cramer ...
Virgolin, Marco, Pissis, Solon P.
openaire +2 more sources
İzmir İktisat Dergisi, 2019 Gezgin satıcı problemi, optimizasyon alanında araştırmacı ve akademisyenler tarafından üzerinde uzun yıllardır yoğun olarak çalışılan çözümü zor (NP-hard) bir problemdir.
Meryem PULAT, İpek DEVECİ KOCAKOÇ
doaj +1 more source
Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-Hard
IET Information SecurityFeedback shift registers (FSRs) are used as a fundamental component in electronics and confidential communication. A FSR f is said to be reducible if all the output sequences of another FSR g can also be generated by f and the FSR g costs less memory ...
Lin Wang
doaj +1 more source