NDLI: A graph for NP-complete problems

Please wait, while we are loading the content...

Implementation of a linear transitive closure algorithm in relational database design

The generation of rules for intelligent help based on task analysis

Perfect page placement

Design and implementation of a graphical user interface for a timing tool

An internet accessible remote controlled home automation system

Toward a unified approach to coupling

Game-based methods for teaching data structures

Fuzzzy constraint network topology and evolutionary hill-climbing

Compression of one-dimensional ECG signals using two-dimensional representations

TUMS: testing using mutant schemata

Design and model for a computer supported cooperative environment for CASE and CAD applications

A tightly secure object-oriented data model using both discretionary and mandatory security methodologies

Java dynamic LVT optimization

ImpRes: supporting services in IPv6 using the flow label and hop-by-hop option fields

I want it all and I want it now!: data retrieval in a distributed multimedia database system

Computer-aided software engineering in a computer supported cooperative environment

Incorporating object relationship notation (ORN) into SQL

Operators in an extended entity-relationship model and their applications

Hybrid evolutionary path planning via visibility-based repair

Disk scheduling revisited: can $O(n^{2})$ algorithms compete?

Graphical representation and storage issues in object-oriented rule modeling

A programmable telephone rate meter: a hardware/software codesign case study

Is the object-oriented paradigm appropriate for scientific software?

Computer-based evaluation forms

Discovering graphic analogies through the use of genetic algorithms

A graph for NP-complete problems

Building object-oriented data structures in Ada 95

Matching groupware to user needs: an exploratory study

Dynamic scheduling of manufacturing processes using dimensional databases

Implementation of distributed applications using Java

Multimedia feedback control in ATM local area networks

Specification and implementation of reusable multimedia presentations

Heterogeneous process migration: issues and an approach

A temporal deductive database model

Filtering SQL via the principles of pandemonium

C-language syntax tutoring using machine learning techniques

A technique for obtaining kernel mode address traces on a pentium-based Linux system

Distributed object-oriented database programming using Java

Software agents and the role of market protocols

A visualization and measurement environment for software engineering

The case for Java as a first language

A comparison of parametric and non-parametric techniques for pattern classification on Canadian agricultural loan data

An algorithm for a special graph

A study on the maintenance of literate programs

Hypertext document generator in a computer supported cooperative work environment

A hyper-text tutorial markup language

Stopping traffic: discretionary access control in a multidatabase system

Manipulation of information representations

Building a registered volume database: an object-oriented octree program

Improving the identification of verbs

Maximum crossing number algorithm on linear array with a reconfigurable pipelined bus system

Interactive Petri net simulation

Fuzzy spatial relations

Linear programming to approximate quadratic 0-1 maximization problems

Analyzing syntax error patterns among novice programmers

Supporting document organization and security in distributed collaborative authoring systems through the use of collaborations

Constructing Delaunay triangulation on the Intel Paragon

A graph for NP-complete problems

Content Provider	ACM Digital Library
Author	Sampath, G.
Abstract	A weighted directed graph $G_{Q}$ = (V, E) is defined for Q, the set of problems known to be NP-complete, with a vertex $v_{i}$ in V being an NP-complete problem $p_{i}$ in Q and the weight of an edge in E being the complexity of the transformation used to prove the NP-completeness of a problem. If the complexity of problem $p_{1}$ relative to problem $p_{2}$ is defined as the minimum complexity of a reduction from $p_{1}$ to $p_{2}$ (considering all paths from $v_{1}$ to $v_{2}$ in V) then the relative complexity graph of Q is the weighted graph $G_{QR}$ = (V, E'), with the weight of edge $e'_{ij}$ being the minimum complexity of $p_{1}$ relative to $p_{2}.$ An $O(n^{3})$ variant of the shortest path problem on directed graphs that is similar to the Floyd algorithm for all-pairs shortest paths is used to construct $G_{QR}.$ $G_{QR}$ can be updated with an $O(n^{2})$ algorithm when a reduction with smaller complexity is found or a new edge is added to the graph, and with an O(n) algorithm if a new vertex (corresponding to the discovery of a new NP-complete problem) is added to the graph.
Starting Page	165
Ending Page	167
Page Count	3
File Format	PDF
ISBN	0897919254
DOI	10.1145/2817460.2817501
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1997-04-02
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Shortest path problem Graph algorithms Reducibility among np-complete problems
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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