Automatically assigned DDC number: 0051
Manually assigned DDC number: 51154
Number of references: 16
Title: Testing Acyclicity of Directed Graphs in Sublinear Time
Author:
Author:
Subject: Michael A. Bender,Dana Ron Testing Acyclicity of Directed Graphs in Sublinear Time
Description: This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs -- acyclicity. Because the choice of representation affects the choice of algorithm, the two main representations of graphs are studied. For the adjacency matrix representation, most appropriate for dense graphs, a testing algorithm is developed that requires query and time complexity of ~ O(1=ffl 2 ), where ffl is a distance parameter independent of the size of the graph. The algorithm, which can probe the adjacency matrix of the graph, accepts every graph that is acyclic, and rejects, with probability at least 2=3, every graph whose adjacency matrix should be modified in at least ffl fraction of its entries so that it become acyclic. For the incidence list representation, most appropriate for sparse graphs, an OmegaGamma jVj 1=3 ) lower bound is proved on the number of queries and the time required for testing, where V...
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 2000-04-12
Pubyear: 2000
Format: ps
Identifier: http://citeseer.ist.psu.edu/274264.html
Source: http://www.eng.tau.ac.il/~danar/Public/dag-long.ps.gz
Language: en
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/488916.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="Efficient Testing of Large Graphs,">
<identifier Org="ISBN:0521698235" Paper_ID="/488916.html" Extracted="0521698235" DDC="511.6" Normalized_DDC="5116" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0898713552" Paper_ID="/488916.html" Extracted="0898713552" DDC="519.4/0285/51" Normalized_DDC="5194028551" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0898714907" Paper_ID="/488916.html" Extracted="0898714907" />
<identifier Org="ISBN:0898715857" Paper_ID="/488916.html" Extracted="0898715857" DDC="005.133" Normalized_DDC="005133" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0898716055" Paper_ID="/488916.html" Extracted="0898716055" />
<identifier Org="ISBN:1402004893" Paper_ID="/488916.html" Extracted="1402004893" DDC="005.75/8" Normalized_DDC="005758" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1581133499" Paper_ID="/488916.html" Extracted="1581133499" />
<identifier Org="ISBN:1581139608" Paper_ID="/488916.html" Extracted="1581139608" />
<identifier Org="ISBN:3540281932" Paper_ID="/488916.html" Extracted="3540281932" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540282394" Paper_ID="/488916.html" Extracted="3540282394" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540336982" Paper_ID="/488916.html" Extracted="3540336982" DDC="511.1" Normalized_DDC="5111" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540405453" Paper_ID="/488916.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />
<identifier Org="ISBN:354041004X" Paper_ID="/488916.html" Extracted="354041004X" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540422870" Paper_ID="/488916.html" Extracted="3540422870" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540424938" Paper_ID="/488916.html" Extracted="3540424938" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540424997" Paper_ID="/488916.html" Extracted="3540424997" DDC="621.39/5" Normalized_DDC="621395" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540441476" Paper_ID="/488916.html" Extracted="3540441476" DDC="004/.07/27" Normalized_DDC="0040727" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540673067" Paper_ID="/488916.html" Extracted="3540673067" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540735445" Paper_ID="/488916.html" Extracted="3540735445" DDC="004" Normalized_DDC="004" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540742077" Paper_ID="/488916.html" Extracted="3540742077" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />
</rec>
<rec ID="/464767.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="Regular Languages Are Testable with a Constant Number of Queries,">
<identifier Org="ISBN:0769514685" Paper_ID="/464767.html" Extracted="0769514685" />
<identifier Org="ISBN:0898715385" Paper_ID="/464767.html" Extracted="0898715385" />
<identifier Org="ISBN:0898715857" Paper_ID="/464767.html" Extracted="0898715857" DDC="005.133" Normalized_DDC="005133" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:1581133499" Paper_ID="/464767.html" Extracted="1581133499" />
<identifier Org="ISBN:1581136749" Paper_ID="/464767.html" Extracted="1581136749" />
<identifier Org="ISBN:1581139608" Paper_ID="/464767.html" Extracted="1581139608" />
<identifier Org="ISBN:1601981821" Paper_ID="/464767.html" Extracted="1601981821" />
<identifier Org="ISBN:3540228497" Paper_ID="/464767.html" Extracted="3540228497" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540229698" Paper_ID="/464767.html" Extracted="3540229698" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540281932" Paper_ID="/464767.html" Extracted="3540281932" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:354041004X" Paper_ID="/464767.html" Extracted="354041004X" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540424709" Paper_ID="/464767.html" Extracted="3540424709" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540441476" Paper_ID="/464767.html" Extracted="3540441476" DDC="004/.07/27" Normalized_DDC="0040727" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540677151" Paper_ID="/464767.html" Extracted="3540677151" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540709177" Paper_ID="/464767.html" Extracted="3540709177" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540792279" Paper_ID="/464767.html" Extracted="3540792279" />
</rec>
<rec ID="/574242.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems,">
<identifier Org="ISBN:0262100924" Paper_ID="/574242.html" Extracted="0262100924" DDC="572.8/01/51" Normalized_DDC="57280151" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:078033762X" Paper_ID="/574242.html" Extracted="078033762X" />
<identifier Org="ISBN:0780383044" Paper_ID="/574242.html" Extracted="0780383044" DDC="670.42" Normalized_DDC="67042" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0792348788" Paper_ID="/574242.html" Extracted="0792348788" DDC="519.7/6" Normalized_DDC="51976" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0792352858" Paper_ID="/574242.html" Extracted="0792352858" DDC="519.7/6" Normalized_DDC="51976" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0821808346" Paper_ID="/574242.html" Extracted="0821808346" DDC="519.7/6" Normalized_DDC="51976" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0898716055" Paper_ID="/574242.html" Extracted="0898716055" />
<identifier Org="ISBN:1584885505" Paper_ID="/574242.html" Extracted="1584885505" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:1595936319" Paper_ID="/574242.html" Extracted="1595936319" />
<identifier Org="ISBN:3540212361" Paper_ID="/574242.html" Extracted="3540212361" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540249982" Paper_ID="/574242.html" Extracted="3540249982" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540405348" Paper_ID="/574242.html" Extracted="3540405348" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540438645" Paper_ID="/574242.html" Extracted="3540438645" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540443894" Paper_ID="/574242.html" Extracted="3540443894" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540677151" Paper_ID="/574242.html" Extracted="3540677151" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />
</rec>
<rec ID="/43945.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="Checking computations in polylogarithmic time,">
<identifier Org="ISBN:0444828419" Paper_ID="/43945.html" Extracted="0444828419" DDC="511.352" Normalized_DDC="511352" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:078033762X" Paper_ID="/43945.html" Extracted="078033762X" />
<identifier Org="ISBN:0821803794" Paper_ID="/43945.html" Extracted="0821803794" DDC="003/.54" Normalized_DDC="00354" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0897913973" Paper_ID="/43945.html" Extracted="0897913973" />
<identifier Org="ISBN:0898713293" Paper_ID="/43945.html" Extracted="0898713293" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1558608176" Paper_ID="/43945.html" Extracted="1558608176" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1581137079" Paper_ID="/43945.html" Extracted="1581137079" DDC="621.381536" Normalized_DDC="621381536" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1584885505" Paper_ID="/43945.html" Extracted="1584885505" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1933019026" Paper_ID="/43945.html" Extracted="1933019026" />
<identifier Org="ISBN:3540201262" Paper_ID="/43945.html" Extracted="3540201262" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540228497" Paper_ID="/43945.html" Extracted="3540228497" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540304959" Paper_ID="/43945.html" Extracted="3540304959" DDC="005.3" Normalized_DDC="0053" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540605738" Paper_ID="/43945.html" Extracted="3540605738" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540606157" Paper_ID="/43945.html" Extracted="3540606157" DDC="005.1/4/015113" Normalized_DDC="00514015113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540632484" Paper_ID="/43945.html" Extracted="3540632484" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354064766X" Paper_ID="/43945.html" Extracted="354064766X" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540661301" Paper_ID="/43945.html" Extracted="3540661301" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3764327987" Paper_ID="/43945.html" Extracted="3764327987" />
</rec>
<rec ID="/15039.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols,">
<identifier Org="ISBN:0818620722" Paper_ID="/15039.html" Extracted="0818620722" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:081862082X" Paper_ID="/15039.html" Extracted="081862082X" />
<identifier Org="ISBN:0818624477" Paper_ID="/15039.html" Extracted="0818624477" />
<identifier Org="ISBN:0821865900" Paper_ID="/15039.html" Extracted="0821865900" DDC="005.8/2" Normalized_DDC="00582" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0824727223" Paper_ID="/15039.html" Extracted="0824727223" />
<identifier Org="ISBN:0897916638" Paper_ID="/15039.html" Extracted="0897916638" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540001425" Paper_ID="/15039.html" Extracted="3540001425" DDC="004.015118" Normalized_DDC="004015118" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540006230" Paper_ID="/15039.html" Extracted="3540006230" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540407707" Paper_ID="/15039.html" Extracted="3540407707" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540544585" Paper_ID="/15039.html" Extracted="3540544585" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540544879" Paper_ID="/15039.html" Extracted="3540544879" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540583254" Paper_ID="/15039.html" Extracted="3540583254" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540606157" Paper_ID="/15039.html" Extracted="3540606157" DDC="005.1/4/015113" Normalized_DDC="00514015113" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540632484" Paper_ID="/15039.html" Extracted="3540632484" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540653856" Paper_ID="/15039.html" Extracted="3540653856" DDC="004.015118" Normalized_DDC="004015118" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540662006" Paper_ID="/15039.html" Extracted="3540662006" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540705821" Paper_ID="/15039.html" Extracted="3540705821" />
<identifier Org="ISBN:354078523X" Paper_ID="/15039.html" Extracted="354078523X" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540853626" Paper_ID="/15039.html" Extracted="3540853626" />
</rec>
<rec ID="/412298.html" Type="inproceedings" CiteSeer_Book="ACM Symposium on Theory of Computing" CiteSeer_Volume="" Title="Spot-Checkers,">
<identifier Org="ISBN:0071361243" Paper_ID="/412298.html" Extracted="0071361243" DDC="796.069" Normalized_DDC="796069" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:0312428235" Paper_ID="/412298.html" Extracted="0312428235" DDC="302.23/2" Normalized_DDC="302232" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:094621106X" Paper_ID="/412298.html" Extracted="094621106X" DDC="305.4/09417" Normalized_DDC="305409417" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:1581130678" Paper_ID="/412298.html" Extracted="1581130678" />
<identifier Org="ISBN:3540282394" Paper_ID="/412298.html" Extracted="3540282394" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:3540405453" Paper_ID="/412298.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:3540729259" Paper_ID="/412298.html" Extracted="3540729259" />
<identifier Org="ISBN:3540734198" Paper_ID="/412298.html" Extracted="3540734198" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.16666666666666666" />
</rec>
<rec ID="/487859.html" Type="article" CiteSeer_Book="Algorithmica" CiteSeer_Volume="20" Title="Approximating Minimum Feedback Sets and Multicuts in Directed Graphs,">
<identifier Org="ISBN:0780331214" Paper_ID="/487859.html" Extracted="0780331214" />
<identifier Org="ISBN:0792359240" Paper_ID="/487859.html" Extracted="0792359240" DDC="519.6/4" Normalized_DDC="51964" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0898714109" Paper_ID="/487859.html" Extracted="0898714109" />
<identifier Org="ISBN:0898715857" Paper_ID="/487859.html" Extracted="0898715857" DDC="005.133" Normalized_DDC="005133" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:1581139608" Paper_ID="/487859.html" Extracted="1581139608" />
<identifier Org="ISBN:1848009976" Paper_ID="/487859.html" Extracted="1848009976" DDC="511/.54" Normalized_DDC="51154" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540223398" Paper_ID="/487859.html" Extracted="3540223398" DDC="518/.1" Normalized_DDC="5181" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540230718" Paper_ID="/487859.html" Extracted="3540230718" DDC="519.5/44" Normalized_DDC="519544" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540280618" Paper_ID="/487859.html" Extracted="3540280618" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540314253" Paper_ID="/487859.html" Extracted="3540314253" DDC="511/.5" Normalized_DDC="5115" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540405453" Paper_ID="/487859.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540438645" Paper_ID="/487859.html" Extracted="3540438645" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540443894" Paper_ID="/487859.html" Extracted="3540443894" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540677151" Paper_ID="/487859.html" Extracted="3540677151" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540725032" Paper_ID="/487859.html" Extracted="3540725032" />
<identifier Org="ISBN:3540734198" Paper_ID="/487859.html" Extracted="3540734198" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:354079722X" Paper_ID="/487859.html" Extracted="354079722X" DDC="530.11" Normalized_DDC="53011" Normalized_Weight="0.07692307692307693" />
</rec>
<rec ID="/146976.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="New sampling-based summary statistics for improving approximate query answers,">
<identifier Org="ISBN:0120884690" Paper_ID="/146976.html" Extracted="0120884690" />
<identifier Org="ISBN:0127224424" Paper_ID="/146976.html" Extracted="0127224424" />
<identifier Org="ISBN:0262693143" Paper_ID="/146976.html" Extracted="0262693143" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0898715687" Paper_ID="/146976.html" Extracted="0898715687" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:1558607153" Paper_ID="/146976.html" Extracted="1558607153" />
<identifier Org="ISBN:1558608044" Paper_ID="/146976.html" Extracted="1558608044" />
<identifier Org="ISBN:1558608699" Paper_ID="/146976.html" Extracted="1558608699" />
<identifier Org="ISBN:1581130627" Paper_ID="/146976.html" Extracted="1581130627" />
<identifier Org="ISBN:1581137273" Paper_ID="/146976.html" Extracted="1581137273" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540210474" Paper_ID="/146976.html" Extracted="3540210474" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540236643" Paper_ID="/146976.html" Extracted="3540236643" DDC="005.758" Normalized_DDC="005758" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540433244" Paper_ID="/146976.html" Extracted="3540433244" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540433694" Paper_ID="/146976.html" Extracted="3540433694" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540440453" Paper_ID="/146976.html" Extracted="3540440453" DDC="005.75/8" Normalized_DDC="005758" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540441239" Paper_ID="/146976.html" Extracted="3540441239" DDC="658.4/038/0285574" Normalized_DDC="65840380285574" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540441808" Paper_ID="/146976.html" Extracted="3540441808" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540694765" Paper_ID="/146976.html" Extracted="3540694765" />
<identifier Org="ISBN:3540734503" Paper_ID="/146976.html" Extracted="3540734503" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540744495" Paper_ID="/146976.html" Extracted="3540744495" DDC="511/.6" Normalized_DDC="5116" Normalized_Weight="0.08333333333333333" />
</rec>
<rec ID="/321761.html" Type="article" CiteSeer_Book="DIMACS Series in Discrete Mathematics and Theoretical Computer Science Special Issue on External Memory Algorithms and Visualization" CiteSeer_Volume="A" Title="Synopsis Data Structures for Massive Data Sets,">
<identifier Org="ISBN:0821811843" Paper_ID="/321761.html" Extracted="0821811843" DDC="005.4/2" Normalized_DDC="00542" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0898715385" Paper_ID="/321761.html" Extracted="0898715385" />
<identifier Org="ISBN:0898715687" Paper_ID="/321761.html" Extracted="0898715687" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1558606157" Paper_ID="/321761.html" Extracted="1558606157" />
<identifier Org="ISBN:1581130627" Paper_ID="/321761.html" Extracted="1581130627" />
<identifier Org="ISBN:1581134096" Paper_ID="/321761.html" Extracted="1581134096" />
<identifier Org="ISBN:1581135297" Paper_ID="/321761.html" Extracted="1581135297" />
<identifier Org="ISBN:3540305106" Paper_ID="/321761.html" Extracted="3540305106" DDC="004/.36" Normalized_DDC="00436" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540322124" Paper_ID="/321761.html" Extracted="3540322124" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:354033288X" Paper_ID="/321761.html" Extracted="354033288X" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540407979" Paper_ID="/321761.html" Extracted="3540407979" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540408061" Paper_ID="/321761.html" Extracted="3540408061" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540433244" Paper_ID="/321761.html" Extracted="3540433244" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540671412" Paper_ID="/321761.html" Extracted="3540671412" DDC="004.01511" Normalized_DDC="00401511" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540694765" Paper_ID="/321761.html" Extracted="3540694765" />
<identifier Org="ISBN:3540710086" Paper_ID="/321761.html" Extracted="3540710086" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540755195" Paper_ID="/321761.html" Extracted="3540755195" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.09090909090909091" />
</rec>
<rec ID="/148615.html" Type="article" CiteSeer_Book="Combinatorica" CiteSeer_Volume="18" Title="Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs,">
<identifier Org="ISBN:078033762X" Paper_ID="/148615.html" Extracted="078033762X" />
<identifier Org="ISBN:0792359240" Paper_ID="/148615.html" Extracted="0792359240" DDC="519.6/4" Normalized_DDC="51964" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0898715857" Paper_ID="/148615.html" Extracted="0898715857" DDC="005.133" Normalized_DDC="005133" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:1848009976" Paper_ID="/148615.html" Extracted="1848009976" DDC="511/.54" Normalized_DDC="51154" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540261990" Paper_ID="/148615.html" Extracted="3540261990" DDC="519.77" Normalized_DDC="51977" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540443894" Paper_ID="/148615.html" Extracted="3540443894" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540613102" Paper_ID="/148615.html" Extracted="3540613102" DDC="519.7/7" Normalized_DDC="51977" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540654313" Paper_ID="/148615.html" Extracted="3540654313" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540677151" Paper_ID="/148615.html" Extracted="3540677151" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:354079722X" Paper_ID="/148615.html" Extracted="354079722X" DDC="530.11" Normalized_DDC="53011" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540922474" Paper_ID="/148615.html" Extracted="3540922474" />
</rec>
<rec ID="/92370.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="Property Testing and Its Connection to Learning and Approximation,">
<identifier Org="ISBN:078033762X" Paper_ID="/92370.html" Extracted="078033762X" />
<identifier Org="ISBN:0821809164" Paper_ID="/92370.html" Extracted="0821809164" DDC="519.2" Normalized_DDC="5192" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0898713552" Paper_ID="/92370.html" Extracted="0898713552" DDC="519.4/0285/51" Normalized_DDC="5194028551" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0898716055" Paper_ID="/92370.html" Extracted="0898716055" />
<identifier Org="ISBN:0898716101" Paper_ID="/92370.html" Extracted="0898716101" />
<identifier Org="ISBN:3540228942" Paper_ID="/92370.html" Extracted="3540228942" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540229698" Paper_ID="/92370.html" Extracted="3540229698" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540241310" Paper_ID="/92370.html" Extracted="3540241310" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540282394" Paper_ID="/92370.html" Extracted="3540282394" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540405453" Paper_ID="/92370.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540407200" Paper_ID="/92370.html" Extracted="3540407200" />
<identifier Org="ISBN:3540422870" Paper_ID="/92370.html" Extracted="3540422870" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540424938" Paper_ID="/92370.html" Extracted="3540424938" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540424997" Paper_ID="/92370.html" Extracted="3540424997" DDC="621.39/5" Normalized_DDC="621395" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540441476" Paper_ID="/92370.html" Extracted="3540441476" DDC="004/.07/27" Normalized_DDC="0040727" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540663290" Paper_ID="/92370.html" Extracted="3540663290" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540673067" Paper_ID="/92370.html" Extracted="3540673067" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540729259" Paper_ID="/92370.html" Extracted="3540729259" />
<identifier Org="ISBN:3540850961" Paper_ID="/92370.html" Extracted="3540850961" />
<identifier Org="ISBN:3540853626" Paper_ID="/92370.html" Extracted="3540853626" />
</rec>
<rec ID="/670379.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="Property testing in bounded degree graphs,">
<identifier Org="ISBN:0821809164" Paper_ID="/670379.html" Extracted="0821809164" DDC="519.2" Normalized_DDC="5192" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0897918886" Paper_ID="/670379.html" Extracted="0897918886" />
<identifier Org="ISBN:0898713552" Paper_ID="/670379.html" Extracted="0898713552" DDC="519.4/0285/51" Normalized_DDC="5194028551" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:0898714907" Paper_ID="/670379.html" Extracted="0898714907" />
<identifier Org="ISBN:0898716055" Paper_ID="/670379.html" Extracted="0898716055" />
<identifier Org="ISBN:1402004893" Paper_ID="/670379.html" Extracted="1402004893" DDC="005.75/8" Normalized_DDC="005758" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:1581130678" Paper_ID="/670379.html" Extracted="1581130678" />
<identifier Org="ISBN:3540282394" Paper_ID="/670379.html" Extracted="3540282394" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540336982" Paper_ID="/670379.html" Extracted="3540336982" DDC="511.1" Normalized_DDC="5111" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540405453" Paper_ID="/670379.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:354041004X" Paper_ID="/670379.html" Extracted="354041004X" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540441476" Paper_ID="/670379.html" Extracted="3540441476" DDC="004/.07/27" Normalized_DDC="0040727" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540663290" Paper_ID="/670379.html" Extracted="3540663290" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540671412" Paper_ID="/670379.html" Extracted="3540671412" DDC="004.01511" Normalized_DDC="00401511" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540673067" Paper_ID="/670379.html" Extracted="3540673067" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540705740" Paper_ID="/670379.html" Extracted="3540705740" />
<identifier Org="ISBN:3540709177" Paper_ID="/670379.html" Extracted="3540709177" DDC="004" Normalized_DDC="004" Normalized_Weight="0.08333333333333333" />
<identifier Org="ISBN:3540853626" Paper_ID="/670379.html" Extracted="3540853626" />
</rec>
<rec ID="/107709.html" Type="article" CiteSeer_Book="Information Processing Letters" CiteSeer_Volume="51" Title="Approximations for the Maximum Acyclic Subgraph Problem,">
<identifier Org="ISBN:0898716055" Paper_ID="/107709.html" Extracted="0898716055" />
<identifier Org="ISBN:1584884061" Paper_ID="/107709.html" Extracted="1584884061" DDC="572.8" Normalized_DDC="5728" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:1595936319" Paper_ID="/107709.html" Extracted="1595936319" />
<identifier Org="ISBN:3540424946" Paper_ID="/107709.html" Extracted="3540424946" DDC="004" Normalized_DDC="004" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:3540428666" Paper_ID="/107709.html" Extracted="3540428666" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:3540437444" Paper_ID="/107709.html" Extracted="3540437444" DDC="006.3/7" Normalized_DDC="00637" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:3540654313" Paper_ID="/107709.html" Extracted="3540654313" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:3540677151" Paper_ID="/107709.html" Extracted="3540677151" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.16666666666666666" />
</rec>
<rec ID="/705569.html" Type="article" CiteSeer_Book="Journal of Computer and System Sciences" CiteSeer_Volume="61" Title="Testing Problems with Sublearning Sample Complexity,">
<identifier Org="ISBN:3540405453" Paper_ID="/705569.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="1.0" />
</rec>
<rec ID="/701513.html" Type="article" CiteSeer_Book="Random Structures and Algorithms" CiteSeer_Volume="20" Title="Testing the diameter of graphs,">
<identifier Org="ISBN:0898713552" Paper_ID="/701513.html" Extracted="0898713552" DDC="519.4/0285/51" Normalized_DDC="5194028551" Normalized_Weight="0.1" />
<identifier Org="ISBN:0898714907" Paper_ID="/701513.html" Extracted="0898714907" />
<identifier Org="ISBN:0898716055" Paper_ID="/701513.html" Extracted="0898716055" />
<identifier Org="ISBN:1402004893" Paper_ID="/701513.html" Extracted="1402004893" DDC="005.75/8" Normalized_DDC="005758" Normalized_Weight="0.1" />
<identifier Org="ISBN:1601981821" Paper_ID="/701513.html" Extracted="1601981821" />
<identifier Org="ISBN:2856291562" Paper_ID="/701513.html" Extracted="2856291562" />
<identifier Org="ISBN:3540228497" Paper_ID="/701513.html" Extracted="3540228497" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540228942" Paper_ID="/701513.html" Extracted="3540228942" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540336982" Paper_ID="/701513.html" Extracted="3540336982" DDC="511.1" Normalized_DDC="5111" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540405453" Paper_ID="/701513.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540407707" Paper_ID="/701513.html" Extracted="3540407707" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540441476" Paper_ID="/701513.html" Extracted="3540441476" DDC="004/.07/27" Normalized_DDC="0040727" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540663290" Paper_ID="/701513.html" Extracted="3540663290" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540677151" Paper_ID="/701513.html" Extracted="3540677151" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540853626" Paper_ID="/701513.html" Extracted="3540853626" />
</rec>
<rec ID="/541504.html" Type="article" CiteSeer_Book="SIAM Journal on Computing" CiteSeer_Volume="25" Title="Robust Characterizations of Polynomials with Applications to Program Testing,">
<identifier Org="ISBN:082182872X" Paper_ID="/541504.html" Extracted="082182872X" DDC="511.3/52" Normalized_DDC="511352" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0898715385" Paper_ID="/541504.html" Extracted="0898715385" />
<identifier Org="ISBN:1581130678" Paper_ID="/541504.html" Extracted="1581130678" />
<identifier Org="ISBN:1581138520" Paper_ID="/541504.html" Extracted="1581138520" />
<identifier Org="ISBN:3540228942" Paper_ID="/541504.html" Extracted="3540228942" DDC="004/.01/51" Normalized_DDC="0040151" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540229698" Paper_ID="/541504.html" Extracted="3540229698" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540405453" Paper_ID="/541504.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540406719" Paper_ID="/541504.html" Extracted="3540406719" />
<identifier Org="ISBN:3540416951" Paper_ID="/541504.html" Extracted="3540416951" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540424997" Paper_ID="/541504.html" Extracted="3540424997" DDC="621.39/5" Normalized_DDC="621395" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540642757" Paper_ID="/541504.html" Extracted="3540642757" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540671412" Paper_ID="/541504.html" Extracted="3540671412" DDC="004.01511" Normalized_DDC="00401511" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540673067" Paper_ID="/541504.html" Extracted="3540673067" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540705740" Paper_ID="/541504.html" Extracted="3540705740" />
<identifier Org="ISBN:3540792279" Paper_ID="/541504.html" Extracted="3540792279" />
<identifier Org="ISBN:3540853626" Paper_ID="/541504.html" Extracted="3540853626" />
</rec>
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Testing Acyclicity of Directed Graphs in Sublinear Time">
<identifier Org="ISBN:1402004893" Paper_ID="SELF" Extracted="1402004893" DDC="005.75/8" Normalized_DDC="005758" Normalized_Weight="0.25" />
<identifier Org="ISBN:3540405453" Paper_ID="SELF" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.25" />
<identifier Org="ISBN:3540441476" Paper_ID="SELF" Extracted="3540441476" DDC="004/.07/27" Normalized_DDC="0040727" Normalized_Weight="0.25" />
<identifier Org="ISBN:3540677151" Paper_ID="SELF" Extracted="3540677151" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.25" />
</rec>
</references_metadata>