DOI: 10.1007/3-540-56939-1_63. The complexity of approximating PSPACE-complete problems for hierarchical specifications

The complexity of approximating PSPACE-complete problems for hierarchical specifications

10.1007/3-540-56939-1_63

Crossref book-chapter

Springer Berlin Heidelberg

Lecture Notes in Computer Science (297)

Bibliography

Marathe, M. V., Hunt, H. B., & Ravi, S. S. (1993). The complexity of approximating PSPACE-complete problems for hierarchical specifications. Automata, Languages and Programming, 76â87.

Authors 3

M. V. Marathe (first)
H. B. Hunt (additional)
S. S. Ravi (additional)

References 20 Referenced 6

R.J. Anderson and E.W. Mayr “Approximating P-complete problems,” Tech Report, Stanford University, 1986.
J.L. Bentley, T. Ottmann, P. Widmayer, “The Complexity of Manipulating Hierarchically Defined set of Intervals,” Advances in Computing Research, ed. F.P. Preparata Vol. 1, (1983), pp. 127–158.
A. Condon, J. Feigenbaum, C. Lund and P. Shor, “Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions”, to appear in Proc. 25th ACM Symposium on Theory of Computing, 1993. (10.1145/167088.167190)
H. Galperin and A. Wigderson, “Succinct Representation of Graphs,” Information and Control, Vol. 56, 1983, pp. 183–198. (10.1016/S0019-9958(83)80004-7) / Information and Control by H. Galperin (1983)
M.R. Garey, D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco CA, 1979. / Computers and Intractability. A Guide to the Theory of NP-Completeness by M. R. Garey (1979)
F. Höfting, T. Lengauer and E. Wanke, “Processing of Hierarchically Defined Graphs and Graph Families”, in Data Structures and Efficient Algorithms (Final Report on the DFG Special Joint Initiative), LNCS 594, Springer-Verlag, 1992, pp. 44–69. (10.1007/3-540-55488-2_21)
H.B. Hunt III, V. Radhakrishnan, R.E. Stearns, “On The Complexity of Generalized Satisfiability and Hierarchically Specified Generalized Satisfiability Problems,” in preparation.
R.M. Karp, A. Wigderson, “A Fast Parallel Algorithm for the Maximal Independent Set Problem”, J.ACM, Vol. 32, No.4, July 1985, pp. 762–773. (10.1145/4221.4226) / J.ACM by R. M. Karp (1985)
L. Kirousis, M. Serna and P. Spirakis, “The Parallel Complexity of the Subgraph Connectivity problem,” Proc. 30th IEEE-FOCS, 1989, pp. 294–299 (10.1109/SFCS.1989.63493)
T. Lengauer and C. Weiner, “Efficient Solutions hierarchical systems of linear equations,” Computing, Vol 39, 1987, pp. 111–132. (10.1007/BF02310101) / Computing by T. Lengauer (1987)
T. Lengauer, K.W. Wagner, “The correlation between the complexities of non-hierarchical and hierarchical versions of graph problems”, JCSS, Vol. 44 1992, pp. 63–93. / JCSS by T. Lengauer (1992)
T. Lengauer, “Hierarchical Planarity Testing,” J.ACM, Vol. 36, No.3, July 1989, pp. 474–509. (10.1145/65950.65952) / J.ACM by T. Lengauer (1989)
T. Lengauer, “Efficient Solutions for Connectivity Problems for Hierarchically Defined Graphs,” SIAM J. Computing, Vol. 17, No. 6, 1988, pp. 1063–1080. (10.1137/0217068) / SIAM J. Computing by T. Lengauer (1988)
T. Lengauer, “Efficient Algorithms for Finding Minimum Spanning Forests of Hierarchically Defined graphs,” Journal of Algorithms, Vol. 8, 1987, pp. 260–284. (10.1016/0196-6774(87)90042-3) / Journal of Algorithms by T. Lengauer (1987)
T. Lengauer, “Exploiting Hierarchy in VLSI Design,” Proc. AWOC '86, LNCS 227, Springer-Verlag, 1986, pp. 180–193. (10.1007/3-540-16766-8_16)
M. Serna, “Approximating Linear Programming is log-space complete for P,” Inf. Proc. Letters, Vol. 37, No. 4, 1991, pp. 233–236. (10.1016/0020-0190(91)90194-M) / Inf. Proc. Letters by M. Serna (1991)
G. Pantziou, P. Spirakis, C. Zaroliagis, “Fast Parallel Approximations of the Maximum Weighted Cut Problem Through Derandomization,” Proc. 9 th Foundations of Software Technology and Theoretical Computer Science, FCT-TCS, 1989, pp. 20–29. (10.1007/3-540-52048-1_29)
K.W. Wagner, “The complexity of Combinatorial Problems with Succinct Input Representation,” Acta Informatica, Vol. 23, No.3, 1986, pp. 325–356. (10.1007/BF00289117) / Acta Informatica by K. W. Wagner (1986)
M. Williams, “Efficient Processing of Hierarchical Graphs,” TR 90-06, Dept of Computer Science, Iowa Sate University. (Parts of the report appeared in WADS'89 and SWAT'90 coauthored with F. Baca.)
M. Yannakakis, “On the Approximation of Maximum Satisfiability,” Proc. Third Annual ACM-SIAM Symp. on Discrete Algorithms, Jan. 1992, pp 1–9.

Dates

Type	When
Created	13 years, 6 months ago (Feb. 26, 2012, 1:57 a.m.)
Deposited	5 years, 6 months ago (Jan. 29, 2020, 4:07 a.m.)
Indexed	5 months ago (March 26, 2025, 7:33 a.m.)
Issued	32 years, 7 months ago (Jan. 1, 1993)
Published	32 years, 7 months ago (Jan. 1, 1993)
Published Online	20 years, 2 months ago (May 28, 2005)
Published Print	32 years, 7 months ago (Jan. 1, 1993)

Funders 0

None

BibTeX

@inbook{Marathe_1993, title={The complexity of approximating PSPACE-complete problems for hierarchical specifications: Extended abstract}, ISBN={9783540478263}, ISSN={1611-3349}, url={http://dx.doi.org/10.1007/3-540-56939-1_63}, DOI={10.1007/3-540-56939-1_63}, booktitle={Automata, Languages and Programming}, publisher={Springer Berlin Heidelberg}, author={Marathe, M. V. and Hunt, H. B. and Ravi, S. S.}, year={1993}, pages={76–87} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        3,
        26
      ]
    ],
    "date-time": "2025-03-26T11:33:45Z",
    "timestamp": 1742988825358,
    "version": "3.40.3"
  },
  "publisher-location": "Berlin, Heidelberg",
  "reference-count": 20,
  "publisher": "Springer Berlin Heidelberg",
  "isbn-type": [
    {
      "type": "print",
      "value": "9783540569398"
    },
    {
      "type": "electronic",
      "value": "9783540478263"
    }
  ],
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1993,
            1,
            1
          ]
        ],
        "date-time": "1993-01-01T00:00:00Z",
        "timestamp": 725846400000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "http://www.springer.com/tdm"
    }
  ],
  "content-domain": {
    "domain": [
      "link.springer.com"
    ],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1993
      ]
    ]
  },
  "DOI": "10.1007/3-540-56939-1_63",
  "type": "book-chapter",
  "created": {
    "date-parts": [
      [
        2012,
        2,
        26
      ]
    ],
    "date-time": "2012-02-26T06:57:03Z",
    "timestamp": 1330239423000
  },
  "page": "76-87",
  "update-policy": "https://doi.org/10.1007/springer_crossmark_policy",
  "source": "Crossref",
  "is-referenced-by-count": 6,
  "title": "The complexity of approximating PSPACE-complete problems for hierarchical specifications",
  "prefix": "10.1007",
  "author": [
    {
      "given": "M. V.",
      "family": "Marathe",
      "sequence": "first",
      "affiliation": []
    },
    {
      "suffix": "III",
      "given": "H. B.",
      "family": "Hunt",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "S. S.",
      "family": "Ravi",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2005,
        5,
        28
      ]
    ]
  },
  "reference": [
    {
      "key": "7_CR1",
      "unstructured": "R.J. Anderson and E.W. Mayr \u201cApproximating P-complete problems,\u201d Tech Report, Stanford University, 1986."
    },
    {
      "key": "7_CR2",
      "unstructured": "J.L. Bentley, T. Ottmann, P. Widmayer, \u201cThe Complexity of Manipulating Hierarchically Defined set of Intervals,\u201d Advances in Computing Research, ed. F.P. Preparata Vol. 1, (1983), pp. 127\u2013158."
    },
    {
      "key": "7_CR3",
      "doi-asserted-by": "crossref",
      "unstructured": "A. Condon, J. Feigenbaum, C. Lund and P. Shor, \u201cProbabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions\u201d, to appear in Proc. 25th ACM Symposium on Theory of Computing, 1993.",
      "DOI": "10.1145/167088.167190"
    },
    {
      "key": "7_CR4",
      "doi-asserted-by": "crossref",
      "first-page": "183",
      "DOI": "10.1016/S0019-9958(83)80004-7",
      "volume": "56",
      "author": "H. Galperin",
      "year": "1983",
      "unstructured": "H. Galperin and A. Wigderson, \u201cSuccinct Representation of Graphs,\u201d Information and Control, Vol. 56, 1983, pp. 183\u2013198.",
      "journal-title": "Information and Control"
    },
    {
      "key": "7_CR5",
      "volume-title": "Computers and Intractability. A Guide to the Theory of NP-Completeness",
      "author": "M. R. Garey",
      "year": "1979",
      "unstructured": "M.R. Garey, D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco CA, 1979."
    },
    {
      "key": "7_CR6",
      "doi-asserted-by": "crossref",
      "unstructured": "F. H\u00f6fting, T. Lengauer and E. Wanke, \u201cProcessing of Hierarchically Defined Graphs and Graph Families\u201d, in Data Structures and Efficient Algorithms (Final Report on the DFG Special Joint Initiative), LNCS 594, Springer-Verlag, 1992, pp. 44\u201369.",
      "DOI": "10.1007/3-540-55488-2_21"
    },
    {
      "key": "7_CR7",
      "unstructured": "H.B. Hunt III, V. Radhakrishnan, R.E. Stearns, \u201cOn The Complexity of Generalized Satisfiability and Hierarchically Specified Generalized Satisfiability Problems,\u201d in preparation."
    },
    {
      "issue": "No.4",
      "key": "7_CR8",
      "doi-asserted-by": "crossref",
      "first-page": "762",
      "DOI": "10.1145/4221.4226",
      "volume": "32",
      "author": "R. M. Karp",
      "year": "1985",
      "unstructured": "R.M. Karp, A. Wigderson, \u201cA Fast Parallel Algorithm for the Maximal Independent Set Problem\u201d, J.ACM, Vol. 32, No.4, July 1985, pp. 762\u2013773.",
      "journal-title": "J.ACM"
    },
    {
      "key": "7_CR9",
      "doi-asserted-by": "crossref",
      "unstructured": "L. Kirousis, M. Serna and P. Spirakis, \u201cThe Parallel Complexity of the Subgraph Connectivity problem,\u201d Proc. 30th IEEE-FOCS, 1989, pp. 294\u2013299",
      "DOI": "10.1109/SFCS.1989.63493"
    },
    {
      "key": "7_CR10",
      "doi-asserted-by": "crossref",
      "first-page": "111",
      "DOI": "10.1007/BF02310101",
      "volume": "39",
      "author": "T. Lengauer",
      "year": "1987",
      "unstructured": "T. Lengauer and C. Weiner, \u201cEfficient Solutions hierarchical systems of linear equations,\u201d Computing, Vol 39, 1987, pp. 111\u2013132.",
      "journal-title": "Computing"
    },
    {
      "key": "7_CR11",
      "first-page": "63",
      "volume": "44",
      "author": "T. Lengauer",
      "year": "1992",
      "unstructured": "T. Lengauer, K.W. Wagner, \u201cThe correlation between the complexities of non-hierarchical and hierarchical versions of graph problems\u201d, JCSS, Vol. 44 1992, pp. 63\u201393.",
      "journal-title": "JCSS"
    },
    {
      "issue": "No.3",
      "key": "7_CR12",
      "doi-asserted-by": "crossref",
      "first-page": "474",
      "DOI": "10.1145/65950.65952",
      "volume": "36",
      "author": "T. Lengauer",
      "year": "1989",
      "unstructured": "T. Lengauer, \u201cHierarchical Planarity Testing,\u201d J.ACM, Vol. 36, No.3, July 1989, pp. 474\u2013509.",
      "journal-title": "J.ACM"
    },
    {
      "issue": "No.6",
      "key": "7_CR13",
      "doi-asserted-by": "crossref",
      "first-page": "1063",
      "DOI": "10.1137/0217068",
      "volume": "17",
      "author": "T. Lengauer",
      "year": "1988",
      "unstructured": "T. Lengauer, \u201cEfficient Solutions for Connectivity Problems for Hierarchically Defined Graphs,\u201d SIAM J. Computing, Vol. 17, No. 6, 1988, pp. 1063\u20131080.",
      "journal-title": "SIAM J. Computing"
    },
    {
      "key": "7_CR14",
      "doi-asserted-by": "crossref",
      "first-page": "260",
      "DOI": "10.1016/0196-6774(87)90042-3",
      "volume": "8",
      "author": "T. Lengauer",
      "year": "1987",
      "unstructured": "T. Lengauer, \u201cEfficient Algorithms for Finding Minimum Spanning Forests of Hierarchically Defined graphs,\u201d Journal of Algorithms, Vol. 8, 1987, pp. 260\u2013284.",
      "journal-title": "Journal of Algorithms"
    },
    {
      "key": "7_CR15",
      "doi-asserted-by": "crossref",
      "unstructured": "T. Lengauer, \u201cExploiting Hierarchy in VLSI Design,\u201d Proc. AWOC '86, LNCS 227, Springer-Verlag, 1986, pp. 180\u2013193.",
      "DOI": "10.1007/3-540-16766-8_16"
    },
    {
      "issue": "No.4",
      "key": "7_CR16",
      "doi-asserted-by": "crossref",
      "first-page": "233",
      "DOI": "10.1016/0020-0190(91)90194-M",
      "volume": "37",
      "author": "M. Serna",
      "year": "1991",
      "unstructured": "M. Serna, \u201cApproximating Linear Programming is log-space complete for P,\u201d Inf. Proc. Letters, Vol. 37, No. 4, 1991, pp. 233\u2013236.",
      "journal-title": "Inf. Proc. Letters"
    },
    {
      "key": "7_CR17",
      "doi-asserted-by": "crossref",
      "unstructured": "G. Pantziou, P. Spirakis, C. Zaroliagis, \u201cFast Parallel Approximations of the Maximum Weighted Cut Problem Through Derandomization,\u201d Proc. 9\n\n                  th\n                \nFoundations of Software Technology and Theoretical Computer Science, FCT-TCS, 1989, pp. 20\u201329.",
      "DOI": "10.1007/3-540-52048-1_29"
    },
    {
      "issue": "No.3",
      "key": "7_CR18",
      "doi-asserted-by": "crossref",
      "first-page": "325",
      "DOI": "10.1007/BF00289117",
      "volume": "23",
      "author": "K. W. Wagner",
      "year": "1986",
      "unstructured": "K.W. Wagner, \u201cThe complexity of Combinatorial Problems with Succinct Input Representation,\u201d Acta Informatica, Vol. 23, No.3, 1986, pp. 325\u2013356.",
      "journal-title": "Acta Informatica"
    },
    {
      "key": "7_CR19",
      "unstructured": "M. Williams, \u201cEfficient Processing of Hierarchical Graphs,\u201d TR 90-06, Dept of Computer Science, Iowa Sate University. (Parts of the report appeared in WADS'89 and SWAT'90 coauthored with F. Baca.)"
    },
    {
      "key": "7_CR20",
      "unstructured": "M. Yannakakis, \u201cOn the Approximation of Maximum Satisfiability,\u201d Proc. Third Annual ACM-SIAM Symp. on Discrete Algorithms, Jan. 1992, pp 1\u20139."
    }
  ],
  "container-title": "Lecture Notes in Computer Science",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/3-540-56939-1_63",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2020,
        1,
        29
      ]
    ],
    "date-time": "2020-01-29T09:07:20Z",
    "timestamp": 1580288840000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://link.springer.com/10.1007/3-540-56939-1_63"
    }
  },
  "subtitle": [
    "Extended abstract"
  ],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1993
      ]
    ]
  },
  "ISBN": [
    "9783540569398",
    "9783540478263"
  ],
  "references-count": 20,
  "URL": "http://dx.doi.org/10.1007/3-540-56939-1_63",
  "relation": {},
  "ISSN": [
    "0302-9743",
    "1611-3349"
  ],
  "subject": [],
  "published": {
    "date-parts": [
      [
        1993
      ]
    ]
  },
  "assertion": [
    {
      "value": "28 May 2005",
      "order": 1,
      "name": "first_online",
      "label": "First Online",
      "group": {
        "name": "ChapterHistory",
        "label": "Chapter History"
      }
    }
  ]
}