Polynomial Complete Consecutive Information Retrieval Problems

DOI10.1137/0206004MaRDI QIDQ4125734zbMATH OpenOpenAlexFDO

Authors Lawrence T. Kou

Publication date 1977

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1813/6035

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Cited in

(29)

• One more polynomial complete consecutive retrieval problem
• Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
• On strings containing all subsets as substrings
• Recognizing graphs with fixed interval number is NP-complete
• A faster algorithm for finding minimum Tucker submatrices
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• On computing optimal linear diagrams
• On Physical Mapping and the consecutive ones property for sparse matrices
• More on the complexity of common superstring and supersequence problems
• Heuristic methods for gang-rip saw arbor design.
• A note on the consecutive ones submatrix problem.
• Heuristic methods to consecutive block minimization
• Iterated local search for consecutive block minimization
• Minimising the number of gap-zeros in binary matrices
• Once more on storage for consecutive retrieval
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• Consecutive retrieval with redundancy: An optimal linear and an optimal cyclic arrangement and their storage space requirements
• Combinatorial optimization models for production scheduling in automated manufacturing systems
• Page-queries as a tool for organizing secondary memory auxiliary databases. I: Algorithmic aspects and architectural framework of query processing
• Page-queries as a tool for organizing secondary memory auxiliary databases. II: Optimal selection of SADB contents
• Preemptive scheduling and antichain polyhedra
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results
• Polynomial-time local-improvement algorithm for consecutive block minimization
• A multichannel storage arrangement scheme of pictorial databases for concurrent spatial match retrieval
• Algorithmic characterizations of interval orderd hypergraphs and applications
• On the storage space requirement of consecutive retrieval with redundancy
• Exponential neighborhood search for consecutive block minimization
• Consecutive block minimization is 1.5-approximable

This page was built for publication: Polynomial Complete Consecutive Information Retrieval Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4125734)