NDLI: On extremal sort sequences

Content Provider	Springer Nature Link
Author	Yun, Minyoung Keum, Young Wook
Copyright Year	2002
Abstract	A sort sequence S$_{n}$ is a sequence of all unordered pairs of indices inI $_{n}$ = {1, 2, ..., n}. With a sort sequence $$S_n = (s_1 ,s_2 ,...,s_{\left( {_2^n } \right)} )$$ , one can associate a predictive sorting algorithm A(S$_{n}$). An execution of the algorithm performs pairwise comparisons of elements in the input setX in the order defined by the sort sequence S$_{n}$ except that the comparisons whose outcomes can be inferred from the results of the preceding comparisons are not performed. A sort sequence is said to be extremal if it maximizes a given objective function. First we consider the extremal sort sequences with respect to the objective function ω(S$_{n}$) — the expected number of active predictions inS $_{n}$. We study ω-extremal sort sequences in terms of their prediction vectors. Then we consider the objective function Ω(S$_{n}$) — the minimum number of active predictions in S$_{n}$ over all input orderings.
Starting Page	239
Ending Page	252
Page Count	14
File Format	PDF
ISSN	12299502
Journal	Journal of Applied Mathematics and Computing
Volume Number	9
Issue Number	1
e-ISSN	18652085
Language	English
Publisher	Springer-Verlag
Publisher Date	2002-01-01
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Sorting graph theory extremal sort sequences Analysis of algorithms and problem complexity Computational Mathematics and Numerical Analysis ApplicationMathematics/Computational Methods of Engineering Theory of Computation Mathematics of Computing
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Networks and Communications Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The characterization of sort sequences

Second best temporally repeated flows

Efficient algorithms to compute all articulation points of a permutation graph

Computation of a (canonical) doubly perfect elimination ordering of a doubly chordal graph

Sequential and parallel algorithms for minimum flows

An efficient algorithm to solve connectivity problem on trapezoid graphs

Maximum weight independent set of circular-arc graph and its application

Engineering Parallel String Sorting

An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs

On extremal sort sequences

Similar Documents

The characterization of sort sequences

Second best temporally repeated flows

Efficient algorithms to compute all articulation points of a permutation graph

Computation of a (canonical) doubly perfect elimination ordering of a doubly chordal graph

Sequential and parallel algorithms for minimum flows

An efficient algorithm to solve connectivity problem on trapezoid graphs

Maximum weight independent set of circular-arc graph and its application

Engineering Parallel String Sorting

An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs

On extremal sort sequences