Article

Free access

Polynomial space polynomial delay algorithms for listing families of graphs

Author:

Leslie Ann GoldbergAuthors Info & Claims

STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing

Pages 218 - 225

https://doi.org/10.1145/167088.167160

Published: 01 June 1993 Publication History

PDF eReader

References

[1]

A. Blass and F~ Harary, Properties of Almost All Graphs and Complexes, Journal of Graph Theory a (1979) 225-240.

Google Scholar

[2]

H. D~ Ebbinghaus, J. Flum, and W. Thomas, Mathematzcal Logic (Springer-Verlag# 1984).

Google Scholar

[3]

R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, SIAM-AMS Proceedings 7, Complexity of Computation (editor, R. Karp) (1974) 43-73.

Google Scholar

[4]

R. Fagin, Probabilities on Finite Models, Journal of Symbohc Logzc 41(1) (1970) 50-58.

Crossref

Google Scholar

[5]

Yu. V. Glebskii, Do I. Kogan, M. I~ Liogon'kii, and V. A. Talanov, Range and Degree of Realizability of Formulas in the Restricted Predicate Calculus, Cybernetics 5 (1969) 142-154.

Google Scholar

[6]

L. A. Goldberg, Efficient Algorithms for Listing Unlabeled Graphs, Journal of Algorithms 13 (1992) 128-143.

Digital Library

Google Scholar

[7]

Y. Gurevich, Zero-One Laws, The Logic in Computer Scmnce Column, Bulletin of the European Association of Theorel#cal Computer Sczence 46 (1992) 90-106.

Google Scholar

[8]

J. Hartmanis, V. Sewelson, N. Immerman, Sparse Sets in NP- P: EXPTIME Versus NEXPTIME, Proceedings of the ACM Symposium On Theory of Computing 15 (1983) 382-391.

Digital Library

Google Scholar

[9]

D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou, On Generating all Maximal Independent Sets, Information Processing Letters 27 (March 1988) 119-123.

Digital Library

Google Scholar

[10]

P. Raghavan, Probabilistic Construction of Deterministic Algorithms: Approximate Packing Integer Programs, Journal of Computer and System Sciences 37 (1988) 130-143.

Digital Library

Google Scholar

[11]

J. Spencer, Ten Lectures on the Probabilistzc Method (SIAM, 1987).

Google Scholar

Cited By

View all

Yamanaka K(2016)Permutation EnumerationEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_735(1559-1564)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_735
Desrosiers CGalinier PHansen PHertz A(2014)Automated generation of conjectures on forbidden subgraph characterizationDiscrete Applied Mathematics10.5555/2747009.2747055162:C(177-194)Online publication date: 10-Jan-2014
https://dl.acm.org/doi/10.5555/2747009.2747055
WASA KKANETA YUNO TARIMURA H(2014)Constant Time Enumeration of Subtrees with Exactly k Nodes in a TreeIEICE Transactions on Information and Systems10.1587/transinf.E97.D.421E97.D:3(421-430)Online publication date: 2014
https://doi.org/10.1587/transinf.E97.D.421
Show More Cited By

Index Terms

Polynomial space polynomial delay algorithms for listing families of graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Randomness, geometry and discrete structures

Recommendations

Distance Hereditary Graphs and the Interlace Polynomial

The vertex-nullity interlace polynomial of a graph, described by Arratia, Bollobás and Sorkin in [3] as evolving from questions of DNA sequencing, and extended to a two-variable interlace polynomial by the same authors in [5], evokes many open ...
On the roots of domination polynomial of graphs

Let G be a graph of order n . A dominating set of G is a subset of vertices of G , say S , such that every vertex in V ( G ) S is adjacent to at least one vertex of S . The domination polynomial of G is the polynomial D ( G , x ) = i = 1 n d ( G , i ) x ...
On chromatic and flow polynomial unique graphs

It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic ...

Comments

Information & Contributors

Information

Published In

STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing

June 1993

812 pages

ISBN:0897915917

DOI:10.1145/167088

Chairmen:
Rao Kosaraju
John Hopkins Univ., Baltimore, MD
,
David Johnson
AT&T Bell Lab.
,
Alok Aggarwal
IBM T. J. Watson Research Center,Yorktown Heights, NY

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC93

Sponsor:

SIGACT

STOC93: 25th Annual ACM Symposium on the Theory of Computing

May 16 - 18, 1993

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
398
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)15

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yamanaka K(2016)Permutation EnumerationEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_735(1559-1564)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_735
Desrosiers CGalinier PHansen PHertz A(2014)Automated generation of conjectures on forbidden subgraph characterizationDiscrete Applied Mathematics10.5555/2747009.2747055162:C(177-194)Online publication date: 10-Jan-2014
https://dl.acm.org/doi/10.5555/2747009.2747055
WASA KKANETA YUNO TARIMURA H(2014)Constant Time Enumeration of Subtrees with Exactly k Nodes in a TreeIEICE Transactions on Information and Systems10.1587/transinf.E97.D.421E97.D:3(421-430)Online publication date: 2014
https://doi.org/10.1587/transinf.E97.D.421
Yamanaka K(2014)Permutation EnumerationEncyclopedia of Algorithms10.1007/978-3-642-27848-8_735-1(1-7)Online publication date: 7-Oct-2014
https://doi.org/10.1007/978-3-642-27848-8_735-1
Wasa KHirata KUno TArimura H(2013)Faster Algorithms for Tree Similarity Based on Compressed Enumeration of Bounded-Sized Ordered SubtreesProceedings of the 6th International Conference on Similarity Search and Applications - Volume 819910.1007/978-3-642-41062-8_8(73-84)Online publication date: 2-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41062-8_8
Wasa KKaneta YUno TArimura H(2012)Constant Time Enumeration of Bounded-Size Subtrees in Trees and Its ApplicationComputing and Combinatorics10.1007/978-3-642-32241-9_30(347-359)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32241-9_30
Georgii ETsuda K(2012)Density‐Based Set Enumeration in Structured DataStatistical and Machine Learning Approaches for Network Analysis10.1002/9781118346990.ch10(261-301)Online publication date: 21-Jun-2012
https://doi.org/10.1002/9781118346990.ch10
Arimura HUno T(2006)An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequenceJournal of Combinatorial Optimization10.1007/s10878-006-9029-113:3(243-262)Online publication date: 9-Dec-2006
https://doi.org/10.1007/s10878-006-9029-1
Arimura HUno T(2005)A polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequenceProceedings of the 16th international conference on Algorithms and Computation10.1007/11602613_73(724-737)Online publication date: 19-Dec-2005
https://dl.acm.org/doi/10.1007/11602613_73

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Distance Hereditary Graphs and the Interlace Polynomial

On the roots of domination polynomial of graphs

On chromatic and flow polynomial unique graphs