@article{newman2006fcs, author = {Newman, MEJ}, interhash = {5003bcb34d28e1e4bc301fafb9a12c72}, intrahash = {090a24e34da3d0ab3d14d61dd3ad3285}, journal = {Physical Review E}, number = 3, pages = 36104, publisher = {APS}, title = {{Finding community structure in networks using the eigenvectors of matrices}}, volume = 74, year = 2006 } @book{Chung:1997, author = {Chung, F. R. K.}, interhash = {0f0fd754924d4dd54bc185bd1c71d00b}, intrahash = {95ef10b5a69a03d8507240b6cf410f8a}, publisher = {American Mathematical Society}, title = {Spectral Graph Theory}, year = 1997 } @misc{Monien_onspectral, author = {Monien, B.}, interhash = {aa800b59576cd3b65d76650dde88313f}, intrahash = {6ae2643d830d183886ee56d87dc4482d}, title = {On Spectral Bounds for the k-Partitioning of Graphs}, year = 2001 } @article{mohar1991lsg, author = {Mohar, B.}, interhash = {571f21e55ceba47912e7729b561be348}, intrahash = {3d63879e040c1a1ccd239ffaffb0189a}, journal = {Graph Theory, Combinatorics, and Applications}, pages = {871--898}, publisher = {New York: Wiley}, title = {{The Laplacian spectrum of graphs}}, volume = 2, year = 1991 } @article{4389477, abstract = {Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications.}, author = {Spielman, D.A.}, doi = {10.1109/FOCS.2007.56}, interhash = {e9b5ea88418a87d0ce763d1525ab3574}, intrahash = {2db3b428400813210d3649d3cb879071}, issn = {0272-5428}, journal = {Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on}, month = {Oct.}, pages = {29-38}, title = {Spectral Graph Theory and its Applications}, year = 2007 } @article{219403, abstract = {The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied computer science. Hypergraph saturation (i.e., given a hypergraph $\cal H$, decide if every subset of vertices is contained in or contains some edge of $\cal H$) is shown to be co-NP-complete. A certain subproblem of hypergraph saturation, the saturation of simple hypergraphs (i.e., Sperner families), is shown to be under polynomial transformation equivalent to transversal hypergraph recognition; i.e., given two hypergraphs ${\cal H}_{1}, {\cal H}_{2}$, decide if the sets in ${\cal H}_{2}$ are all the minimal transversals of ${\cal H}_{1}$. The complexity of the search problem related to the recognition of the transversal hypergraph, the computation of the transversal hypergraph, is an open problem. This task needs time exponential in the input size; it is unknown whether an output-polynomial algorithm exists. For several important subcases, for instance if an upper or lower bound is imposed on the edge size or for acyclic hypergraphs, output-polynomial algorithms are presented. Computing or recognizing the minimal transversals of a hypergraph is a frequent problem in practice, which is pointed out by identifying important applications in database theory, Boolean switching theory, logic, and artificial intelligence (AI), particularly in model-based diagnosis.}, address = {Philadelphia, PA, USA}, author = {Eiter, Thomas and Gottlob, Georg}, doi = {http://dx.doi.org/10.1137/S0097539793250299}, interhash = {76c12a1c1a65d5f3bd9e1682db7ab11c}, intrahash = {cd05f6dae9a4feed33fa7df223ab89ec}, issn = {0097-5397}, journal = {SIAM J. Comput.}, number = 6, pages = {1278--1304}, publisher = {Society for Industrial and Applied Mathematics}, title = {Identifying the Minimal Transversals of a Hypergraph and Related Problems}, url = {http://portal.acm.org/citation.cfm?id=219403}, volume = 24, year = 1995 } @article{kuznetsov2004icd, author = {Kuznetsov, S.O.}, interhash = {25e972f2dc80f7362dae4fd68c4e7f47}, intrahash = {7d4e785ce77ab0df94fd2786c2ea0a7a}, journal = {Journal of Universal Computer Science}, number = 8, pages = {927--933}, title = {{On the intractability of computing the Duquenne-Guigues base}}, volume = 10, year = 2004 } @article{keyhere, abstract = {Implications of a formal context (G,M,I) have a minimal implication basis, called Duquenne-Guigues basis or stem base. It is shown that the problem of deciding whether a set of attributes is a premise of the stem base is in coNP and determining the size of the stem base is polynomially Turingequivalent to a #P-complete problem.}, author = {Kuznetsov, Sergei and Obiedkov, Sergei}, interhash = {621d51fff81b1ed566607b7e18480dbc}, intrahash = {de0a8419ab5d374012b9d05498f840b0}, journal = {Formal Concept Analysis}, pages = {306--308}, title = {Counting Pseudo-intents and #P-completeness}, url = {http://dx.doi.org/10.1007/11671404_21}, year = 2006 } @article{1393768, abstract = {Implications of a formal context obey Armstrong rules, which allows one to define a minimal (in the number of implications) implication basis, called Duquenne-Guigues basis or stem base in the literature. In this paper we show how implications are reduced to functional dependencies and prove that the problem of determining the size of the stem base is a #P-complete problem.}, address = {Amsterdam, The Netherlands, The Netherlands}, author = {Kuznetsov, Sergei O. and Obiedkov, Sergei}, doi = {http://dx.doi.org/10.1016/j.dam.2007.04.014}, interhash = {984c199174cd75cfb8e315494a1a1477}, intrahash = {5cc734b8c96126d43e9b6c1fc91933d9}, issn = {0166-218X}, journal = {Discrete Appl. Math.}, number = 11, pages = {1994--2003}, publisher = {Elsevier Science Publishers B. V.}, title = {Some decision and counting problems of the Duquenne-Guigues basis of implications}, url = {http://portal.acm.org/citation.cfm?id=1393768}, volume = 156, year = 2008 } @article{46243, address = {Amsterdam, The Netherlands, The Netherlands}, author = {Johnson, David S. and Papadimitriou, Christos H.}, doi = {http://dx.doi.org/10.1016/0020-0190(88)90065-8}, interhash = {9c96c160fa3a6124d40e1e8a1b9e1f7f}, intrahash = {3766db2fcdce6f15149ddbd4829ac380}, issn = {0020-0190}, journal = {Inf. Process. Lett.}, number = 3, pages = {119--123}, publisher = {Elsevier North-Holland, Inc.}, title = {On generating all maximal independent sets}, url = {http://portal.acm.org/citation.cfm?id=46241.46243}, volume = 27, year = 1988 } @article{Dias2005240, abstract = {An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X[union or logical sum]Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y[not equal to][empty set], then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. We present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. We also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The methods are based on those by Johnson, Papadimitriou and Yannakakis, in the solution of these two problems for independent sets, instead of bicliques.}, author = {Dias, VĂ¢nia M.F. and de Figueiredo, Celina M.H. and Szwarcfiter, Jayme L.}, doi = {DOI: 10.1016/j.tcs.2005.01.014}, interhash = {db3c1613d7356478877463a22cecedd4}, intrahash = {a60e9536a13fe8f8250b9dac4005130d}, issn = {0304-3975}, journal = {Theoretical Computer Science}, number = {1-3}, pages = {240 - 248}, title = {Generating bicliques of a graph in lexicographic order}, url = {http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280}, volume = 337, year = 2005 } @article{fiedler1975pen, author = {Fiedler, M.}, interhash = {adbb1ba61d363865e2820fedd492a0b1}, intrahash = {225afe6fe72eeacb777f7dab77488bb7}, journal = {Czechoslovak Mathematical Journal}, number = 100, pages = {619--633}, title = {{A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory}}, volume = 25, year = 1975 } @article{haveliwala8090seg, author = {Haveliwala, T.H. and Kamvar, S.D.}, interhash = {0d40b575bd05c58b401f7a78ad3d4627}, intrahash = {bc3bddcd6ea80eea5716492751bdff36}, journal = {A Stanford University Technical Report http://dbpubs. stanford. edu}, title = {{The second eigenvalue of the Google matrix}}, year = 2003 } @inproceedings{coclustering01, address = {New York, NY, USA}, author = {Dhillon, Inderjit S.}, booktitle = {KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining}, citeulike-article-id = {1168281}, doi = {10.1145/502512.502550}, interhash = {d112b6041dab4b4677368c7bf101f1ee}, intrahash = {f07d9cc4813f3ecda75e6f0c8025cece}, isbn = {158113391X}, pages = {269--274}, priority = {2}, publisher = {ACM Press}, title = {Co-clustering documents and words using bipartite spectral graph partitioning}, url = {http://portal.acm.org/citation.cfm?id=502512.502550}, year = 2001 } @unpublished{graphseparators02, author = {Blelloch, Guy}, interhash = {6ad49bdacb2c471d54120be5f5522e47}, intrahash = {80652189b18c675d10b77a96e2adfafc}, title = {Graph Separators}, year = 2002 } @article{partitioning89, author = {Pothen, A. and Simon, H.D. and Liou, K.P.}, interhash = {2f6596b5093c7d16e3817dadf39b8aa2}, intrahash = {7444914fc73fc8ec12a67e5e172c34c0}, journal = {SIAM J. MATRIX ANAL. APPLIC.}, number = 3, pages = {430--452}, title = {{Partitioning Sparse Matrices with Eigenvectors of Graphs}}, url = {http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf }, volume = 11, year = 1990 } @article{journals/tcad/ChanSZ94, author = {Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y.}, date = {2006-05-31}, ee = {http://doi.ieeecomputersociety.org/10.1109/43.310898}, interhash = {f6aa8b385e7b3c62384596f70e7de423}, intrahash = {9aabfb2ef97763db1ae308576b8c0258}, journal = {IEEE Trans. on CAD of Integrated Circuits and Systems}, number = 9, pages = {1088-1096}, title = {Spectral K-way ratio-cut partitioning and clustering.}, url = {http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94}, volume = 13, year = 1994 } @inproceedings{yu2003multiclass, address = {Nice, France}, author = {Yu, Stella X. and Shi, Jianbo}, booktitle = {Proc. International Conference on Computer Vision (ICCV 03)}, interhash = {5ab7b4161bb7cf197db80fe14787e8ac}, intrahash = {d73e1ffedf586cdbaf076277e7c1add6}, month = oct, title = {Multiclass Spectral Clustering}, year = 2003 } @article{journals/tcad/HagenK92, author = {Hagen, Lars W. and Kahng, Andrew B.}, date = {2006-06-19}, ee = {http://doi.ieeecomputersociety.org/10.1109/43.159993}, interhash = {18e3392d9ead65ea9a4c0d7a6062b8eb}, intrahash = {74b87fbffdbc96f4b8ff54c92dc45485}, journal = {IEEE Trans. on CAD of Integrated Circuits and Systems}, number = 9, pages = {1074-1085}, title = {New spectral methods for ratio cut partitioning and clustering.}, url = {http://dblp.uni-trier.de/db/journals/tcad/tcad11.html#HagenK92}, volume = 11, year = 1992 } @inproceedings{1454017, address = {New York, NY, USA}, author = {Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis}, booktitle = {RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems}, doi = {http://doi.acm.org/10.1145/1454008.1454017}, interhash = {8ee38f4ffc05845fcb98f121fb265d48}, intrahash = {e93afe409833a632af02290bbe134cba}, isbn = {978-1-60558-093-7}, location = {Lausanne, Switzerland}, pages = {43--50}, publisher = {ACM}, title = {Tag recommendations based on tensor dimensionality reduction}, url = {http://portal.acm.org/citation.cfm?id=1454017}, year = 2008 }