|
Softpanorama |
May the source be with you, but remember the KISS principle ;-)
|
[Aug 2, 2002] New Links
Journal of Graph Algorithms and Applications Biannual online Journal. Contains many interesting papers.
[Aug 1, 2002] Link updates
[June 7, 2002] Groups & Graphs
is a software package for graphs, digraphs, geometric configurations, combinatorial designs, and their automorphism groups. New in version 3.0 is support for torus maps. A new file structure allows the Mac and Windows versions to read and write the same files. Normalizer and centralizer subgroups can now be computed.
[June 7, 2002] Stas Busygin's NP-Completeness Page
About thirty years ago there was developed a conception designating a hierarchy of complexity classes for problems on finite sets. And so long as we use digital computers with finite memory storing discrete objects to resolve computational problems, it is relevant for any non-trivial algorithm designing. With the current state-of-the-art the most important complexity classes are P (problems solvable in polynomial time) and NP (problems whose solution certificate can be verified in polynomial time). As an example of a P problem we may take a sorting task for a list of numbers. Indeed, successively swapping any disordered pair we can accomplish the task within quadratic time, so the problem is certainly in P. And it is also in NP as when someone gives us another list asserting it is a sorted version of the first one, we can easily look through it to check the order and compare elements to verify are they the same as initial.
Obviously, all P problems are in NP, but is the inverse true... It is one of the most important theoretical problems today and anyone, who shows an ability to resolve it, will be able to get $1M prize from Clay Mathematics Institute.
The most fruitful result of the conception is that complexity classes have so-called complete problems within themselves. A problem of a class is complete if you can solve any other problem of this class in polynomial time having a polynomial time algorithm for the first one. Hence complete problems are hardest in their own classes and as they exist we may choose any of them to advance solving techniques for the entire class. The concept of complete problems for a class is generalized to hard problems for the class by inclusion of all other problems, whose polynomial time algorithm gives polynomial time solvability for the class. So, there are NP-complete and NP-hard problems.
[June 7, 2002] Collection of Lecture Notes, Survey Papers, etc currently maintained by Fedor V. Fomin (fomin@upb.de) . A lot of unique links, especially on graphs, including:
Robin Thomas: Tree-decompositions of Graphs
Jerry Spinrad: A draft of book on graph classes
[May 26, 2002] New and old e-books from FREE Computer and Internet Online Books Download Page
[May 24, 2002] Data Structures and Algorithms authors-titles recent submissions -- Nice archive from Cornell University. Among the papers:
cond-mat/0204181 [abs, pdf] :
Title: Local Search in Unstructured Networks
Authors: Lada A. Adamic, Rajan M. Lukose, Bernardo A. Huberman
Comments: 23 pages, 10 figures, a review of local search strategies in unstructured networks, a contribution to `Handbook of Graphs and Networks: From the Genome to the Internet', eds. S. Bornholdt and H.G. Schuster (Wiley-VCH, Berlin, 2002), to be published
Subj-class: Disordered Systems and Neural Networks; Statistical Mechanics; Networking and Internet Architecturecs.DS/0205050 [abs, ps, pdf, other] :
Title: A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
Authors: S. Fekete, S. Khuller, M. Klemmstein, B. Raghavachari, Neal E. Young
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: Journal of Algorithms 24(2):310-324 (1997)cs.DS/0205048 [abs, ps, pdf, other] :
Title: Huffman Coding with Unequal Letter Costs
Authors: Mordecai Golin, Claire Kenyon, Neal E. Young
Subj-class: Data Structures and Algorithms
ACM-class: F.2.0; E.4; I.4.2
Journal-ref: ACM Symposium on Theory of Computing (2002)cs.DS/0205045 [abs, ps, pdf, other] :
Title: Balancing Minimum Spanning and Shortest Path Trees
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version: ACM-SIAM Symposium on Discrete Algorithms (1993)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: Algorithmica 14(4):305-322 (1995)cs.DS/0205043 [abs, ps, pdf, other] :
Title: Low-Degree Spanning Trees of Small Weight
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version in Symposium on Theory of Computing (1994)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: SIAM J. Computing 25(2):355-368 (1996)cs.DS/0205042 [abs, ps, pdf, other] :
Title: Orienting Graphs to Optimize Reachability
Authors: S. L. Hakimi, E. Schmeichel, Neal E. Young
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: Information Processing Letters 63:229-235 (1997)cs.DS/0205041 [abs, ps, pdf, other] :
Title: Faster Parametric Shortest Path and Minimum Balance Algorithms
Authors: Neal Young, Robert Tarjan, James Orlin
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2; G.1.6
Journal-ref: Networks 21(2):205-221 (1991)cs.DS/0205040 [abs, ps, pdf, other] :
Title: Approximating the Minimum Equivalent Digraph
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version in ACM-SIAM Symposium on Discrete Algorithms (1994)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: SIAM J. Computing 24(4):859-872 (1995)cs.DS/0205045 [abs, ps, pdf, other] :
Title: Balancing Minimum Spanning and Shortest Path Trees
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version: ACM-SIAM Symposium on Discrete Algorithms (1993)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: Algorithmica 14(4):305-322 (1995)cs.DS/0205043 [abs, ps, pdf, other] :
Title: Low-Degree Spanning Trees of Small Weight
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version in Symposium on Theory of Computing (1994)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: SIAM J. Computing 25(2):355-368 (1996)cs.DS/0205033 [abs, ps, pdf, other] :
Title: On-Line File Caching
Authors: Neal E. Young
Comments: ACM-SIAM Symposium on Discrete Algorithms (1998)
Subj-class: Data Structures and Algorithms; Computational Complexity; Networking and Internet Architecture
ACM-class: F.1.2, F.2.0, C.2.0
Journal-ref: Algorithmica 33:371-383 (2002)cs.DS/0205011 [abs, ps, pdf, other] :
Title: On Strongly Connected Digraphs with Bounded Cycle Length
Authors: Samir Khuller, Balaji Raghavachari, Neal Young
Subj-class: Data Structures and Algorithms; Computational Complexity
ACM-class: F.2.0; F.1.3
Journal-ref: Discrete Applied Mathematics 69(3):281-289 (1996)cs.DM/0111061 [abs, ps, pdf, other] :
Title: On a Special Case of the Generalized Neighbourhood Problem
Authors: V. Naidenko, Yu. Orlovich
Comments: 13 pages, 3 figures, in Russian
Subj-class: Discrete Mathematics
ACM-class: G.2.2cs.IR/0108018 [abs, ps, pdf, other] :
Title: Bipartite graph partitioning and data clustering
Authors: H. Zha, X. He, C. Ding, M. Gu, H. Simon
Comments: Proceedings of ACM CIKM 2001, the Tenth International Conference on Information and Knowledge Management, 2001
Subj-class: Information Retrieval; Learning
ACM-class: H.3.3; G.1.3; G.2.2cs.CC/0106048 [abs, pdf] :
Title: On some optimization problems for star-free graphs
Authors: V.G. Naidenko, Yu.L. Orlovich
Comments: 6 pages, in Russian
Subj-class: Computational Complexity; Discrete Mathematics
ACM-class: G.1.2; G.2.2cs.CC/0106045 [abs, ps, pdf, other] :
Title: A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
Authors: Andre Grosse, Joerg Rothe, Gerd Wechsung
Comments: 9 pages, appears in part in an ICTCS 2001 paper by the same authors
Subj-class: Computational Complexity
ACM-class: F.1.3; F.2.2cs.CC/0106041 [abs, ps, pdf, other] :
Title: Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones
Authors: André Grosse, Joerg Rothe, Gerd Wechsung
Comments: 12 pages, appears as part of a ICTCS 2001 paper of the same authors
Subj-class: Computational Complexity
ACM-class: F.1.3; F.2.2
[May 17, 2002] Data Structures in the Web - collection of links
[May 10, 2002] MST Java Project MST 1.0 Calculating a minimum spanning tree from a weighted, undirected graph. by Markus Svensson - Friday, May 10th 2002 06:44 EDT
About: MST is a very simple command line Java application for calculating a minimum spanning tree from a weighted, undirected graph. The graph is read from a standard ASCII text file. One possible minimum spanning tree is then printed to the console.
Download tar.gz archive
Download zip archive
Go To Links
Contact
[Mar 16, 2002] Data Structures and Algorithms Table of Contents a nice e-book by John Morris, 1998
[Mar 16, 2002] Pattern Matching Pointers. link [updated 02/18/2002]
[Feb 18, 2002] R010101 Do Programs Teach Algorithms by Dennis E. Hamilton
What is the relationship between algorithms and their implementations that is important to the mastery of computer programming? Is it foundational merely for computer science or does it inform the development of all successful computing practice? Is there a firm distinction or is it conceptual and qualitative?
Reviewing Sedgewick's approach leads me to explore the separateness of algorithms more closely. I conclude that writing down an algorithm in any form commits one to a framework, like it or not. Formalism is like that.
Even so, I maintain, differentiating statements of algorithms from programs is indispensable. Abstracting algorithms encourages students and practitioners to develop their ability to identify, operate with, and interpret levels of abstractions. It is at the heart of computing.
Copyright © 1996-2008 by Dr. Nikolai Bezroukov. www.softpanorama.org was created as a service to the UN Sustainable Development Networking Programme (SDNP) in the author free time. Submit comments This document is an industrial compilation designed and created exclusively for educational use and is placed under the copyright of the Open Content License(OPL). Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.
Standard disclaimer: The statements, views and opinions presented on this web page are those of the author and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.
Last updated: March 15, 2008