54 lines
3.3 KiB
BibTeX
54 lines
3.3 KiB
BibTeX
|
||
@article{chiba_arboricity_1985,
|
||
title = {Arboricity and {Subgraph} {Listing} {Algorithms}},
|
||
volume = {14},
|
||
issn = {0097-5397},
|
||
url = {https://epubs.siam.org/doi/10.1137/0214017},
|
||
doi = {10.1137/0214017},
|
||
abstract = {We show an algorithm that finds cliques of size (log n/log log n)2 whenever a graph has a clique of size at least n/(log n)b for an arbitrary constant b. This leads to an algorithm that approximates max clique within a factor of O(n(log log n)2/(log n)3), which matches the best approximation ratio known for the chromatic number. The previously best approximation ratio known for max clique was O(n/(log n)2).},
|
||
number = {1},
|
||
urldate = {2024-11-07},
|
||
journal = {SIAM Journal on Computing},
|
||
author = {Chiba, Norishige and Nishizeki, Takao},
|
||
month = feb,
|
||
year = {1985},
|
||
note = {Publisher: Society for Industrial and Applied Mathematics},
|
||
pages = {210--223},
|
||
file = {J053.pdf:/Users/congyu/Zotero/storage/65H5VVYS/J053.pdf:application/pdf},
|
||
}
|
||
|
||
@inproceedings{van_kreveld_finding_1990,
|
||
address = {Berlin, Heidelberg},
|
||
title = {Finding squares and rectangles in sets of points},
|
||
isbn = {978-3-540-46950-6},
|
||
doi = {10.1007/3-540-52292-1_25},
|
||
abstract = {The following problem is studied: Given a set S of n points in the plane, does it contain a subset of four points that form the vertices of a square or rectangle. Both the axis-parallel case and the arbitrarily oriented case are studied. We also investigate extensions to the d-dimensional case. Algorithms are obtained that run in O(n1+1/dlog n) time for axis-parallel squares and O(n2−1/d) time for axis-parallel rectangles. For arbitrarily oriented squares the time bounds are O(n2log n), O n3) and O(nd−1/2β(n)) for d=2, d=3 and d≥4, respectively (where β(n) is related to the inverse of Ackermann's function), whereas the algorithm for arbitrarily oriented rectangles takes time O(ndlogn). Furthermore, it is shown that recognizing axisparallel rectangles is equivalent to recognizing a K2,2-subgraph in a bipartite graph, resulting in a O(‖E‖ √‖E‖) time and O(‖V‖ + ‖E‖) space solution to this problem. Also, combinatorial results on the maximal number of squares and rectangles any point set can contain are given.},
|
||
language = {en},
|
||
booktitle = {Graph-{Theoretic} {Concepts} in {Computer} {Science}},
|
||
publisher = {Springer},
|
||
author = {van Kreveld, Marc J. and de Berg, Mark T.},
|
||
editor = {Nagl, Manfred},
|
||
year = {1990},
|
||
keywords = {Bipartite Graph, Edge Length, Large Subset, Pointer Structure, Small Subset},
|
||
pages = {341--355},
|
||
file = {Full Text PDF:/Users/congyu/Zotero/storage/WA5PCFYP/van Kreveld and de Berg - 1990 - Finding squares and rectangles in sets of points.pdf:application/pdf},
|
||
}
|
||
|
||
@article{furedi_new_1996,
|
||
title = {New {Asymptotics} for {Bipartite} {Turán} {Numbers}},
|
||
volume = {75},
|
||
copyright = {https://www.elsevier.com/tdm/userlicense/1.0/},
|
||
issn = {00973165},
|
||
url = {https://linkinghub.elsevier.com/retrieve/pii/S0097316596900679},
|
||
doi = {10.1006/jcta.1996.0067},
|
||
language = {en},
|
||
number = {1},
|
||
urldate = {2024-11-14},
|
||
journal = {Journal of Combinatorial Theory, Series A},
|
||
author = {Füredi, Zoltán},
|
||
month = jul,
|
||
year = {1996},
|
||
pages = {141--144},
|
||
file = {PDF:/Users/congyu/Zotero/storage/STCZUQN4/Füredi - 1996 - New Asymptotics for Bipartite Turán Numbers.pdf:application/pdf},
|
||
}
|