-
Notifications
You must be signed in to change notification settings - Fork 0
/
cited.bib
209 lines (195 loc) · 11 KB
/
cited.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
@article{jordan_combinatorial_nodate,
title = {{COMBINATORIAL} {RIGIDITY}: {GRAPHS} {AND} {MATROIDS} {IN} {THE} {THEORY} {OF} {RIGID} {FRAMEWORKS}},
language = {en},
author = {Jordan, Tibor}
}
@article{servatiusTwodimensionalGenericRigidity1991,
title = {On the two-dimensional generic rigidity matroid and its dual},
volume = {53},
issn = {00958956},
url = {https://linkinghub.elsevier.com/retrieve/pii/009589569190056P},
doi = {10.1016/0095-8956(91)90056-P},
language = {en},
number = {1},
urldate = {2023-10-24},
journal = {Journal of Combinatorial Theory, Series B},
author = {Servatius, Brigitte},
month = sep,
year = {1991},
pages = {106--113}
}
@article{gu_spanning_2018,
title = {Spanning rigid subgraph packing and sparse subgraph covering},
volume = {32},
issn = {0895-4801, 1095-7146},
url = {http://arxiv.org/abs/1405.0247},
doi = {10.1137/17M1134196},
abstract = {Rigidity, arising in discrete geometry, is the property of a structure that does not flex. Laman provides a combinatorial characterization of rigid graphs in the Euclidean plane, and thus rigid graphs in the Euclidean plane have applications in graph theory. We discover a sufficient partition condition of packing spanning rigid subgraphs and spanning trees. As a corollary, we show that a simple graph \$G\$ contains a packing of \$k\$ spanning rigid subgraphs and \$l\$ spanning trees if \$G\$ is \$(4k+2l)\$-edge-connected, and \$G-Z\$ is essentially \$(6k+2l - 2k{\textbar}Z{\textbar})\$-edge-connected for every \$Z{\textbackslash}subset V(G)\$. Thus every \$(4k+2l)\$-connected and essentially \$(6k+2l)\$-connected graph \$G\$ contains a packing of \$k\$ spanning rigid subgraphs and \$l\$ spanning trees. Utilizing this, we show that every \$6\$-connected and essentially \$8\$-connected graph \$G\$ contains a spanning tree \$T\$ such that \$G-E(T)\$ is \$2\$-connected. These improve some previous results. Sparse subgraph covering problems are also studied.},
number = {2},
urldate = {2023-12-06},
journal = {SIAM Journal on Discrete Mathematics},
author = {Gu, Xiaofeng},
month = jan,
year = {2018},
note = {arXiv:1405.0247 [math]},
keywords = {Mathematics - Combinatorics, 05C40, 05C70},
pages = {1305--1313},
annote = {Comment: 12 pages}
}
@book{schrijver_combinatorial_2003,
address = {Berlin Heidelberg},
series = {Algorithms and combinatorics},
title = {Combinatorial optimization: polyhedra and efficiency},
isbn = {978-3-540-44389-6},
shorttitle = {Combinatorial optimization},
language = {en},
number = {24},
publisher = {Springer},
author = {Schrijver, Alexander},
year = {2003}
}
@article{lee_pebble_2008,
title = {Pebble game algorithms and sparse graphs},
volume = {308},
issn = {0012365X},
url = {https://linkinghub.elsevier.com/retrieve/pii/S0012365X07005602},
doi = {10.1016/j.disc.2007.07.104},
abstract = {A multi-graph G on n vertices is (k, )-sparse if every subset of n n vertices spans at most kn − edges. G is tight if, in addition, it has exactly kn − edges. For integer values k and ∈ [0, 2k), we characterize the (k, )-sparse graphs via a family of simple, elegant and efficient algorithms called the (k, )-pebble games.},
language = {en},
number = {8},
urldate = {2023-10-24},
journal = {Discrete Mathematics},
author = {Lee, Audrey and Streinu, Ileana},
month = apr,
year = {2008},
pages = {1425--1437}
}
@book{frank_connections_2011,
title = {Connections in {Combinatorial} {Optimization}},
isbn = {978-0-19-920527-1},
url = {http://scholar.google.com/scholar?hl=en&btnG=Search&q=intitle:Connections+in+Combinatorial+Optimization#0},
urldate = {2014-07-17},
publisher = {Oxford University Press},
author = {Frank, András},
year = {2011},
note = {Publication Title: Oxford Lecture Series in Mathematics and Its Applications},
file = {PDF:/Users/congyu/Zotero/storage/7WP6YL2K/2011-Connections_in_Combinatorial_Optimization.pdf:application/pdf}
}
@misc{ikeshita_count_2016,
title = {Count {Matroids} of {Group}-{Labeled} {Graphs}},
url = {http://arxiv.org/abs/1507.01259},
doi = {10.48550/arXiv.1507.01259},
abstract = {A graph \$G=(V,E)\$ is called \$(k,{\textbackslash}ell)\$-sparse if \${\textbar}F{\textbar}{\textbackslash}leq k{\textbar}V(F){\textbar}-{\textbackslash}ell\$ for any nonempty \$F{\textbackslash}subseteq E\$, where \$V(F)\$ denotes the set of vertices incident to \$F\$. It is known that the family of the edge sets of \$(k,{\textbackslash}ell)\$-sparse subgraphs forms the family of independent sets of a matroid, called the \$(k,{\textbackslash}ell)\$-count matroid of \$G\$. In this paper we shall investigate lifts of the \$(k,{\textbackslash}ell)\$-count matroid by using group labelings on the edge set. By introducing a new notion called near-balancedness, we shall identify a new class of matroids, where the independence condition is described as a count condition of the form \${\textbar}F{\textbar}{\textbackslash}leq k{\textbar}V(F){\textbar}-{\textbackslash}ell +{\textbackslash}alpha\_\{{\textbackslash}psi\}(F)\$ for some function \${\textbackslash}alpha\_\{{\textbackslash}psi\}\$ determined by a given group labeling \${\textbackslash}psi\$ on \$E\$.},
urldate = {2024-03-18},
publisher = {arXiv},
author = {Ikeshita, Rintaro and Tanigawa, Shin-ichi},
month = jun,
year = {2016},
note = {arXiv:1507.01259 [math]},
keywords = {05B35, Mathematics - Combinatorics},
file = {arXiv Fulltext PDF:/Users/congyu/Zotero/storage/JKCF6LLS/Ikeshita and Tanigawa - 2016 - Count Matroids of Group-Labeled Graphs.pdf:application/pdf}
}
@article{Bonin_Savitsky_2016,
title = {An infinite family of excluded minors for strong base-orderability},
volume = {488},
issn = {00243795},
url = {https://linkinghub.elsevier.com/retrieve/pii/S0024379515005935},
doi = {10.1016/j.laa.2015.09.055},
journal = {Linear Algebra and its Applications},
author = {Bonin, Joseph E. and Savitsky, Thomas J.},
year = {2016},
month = jan,
pages = {396–429},
language = {en}
}
@article{Woodall_1974,
title = {An exchange theorem for bases of matroids},
volume = {16},
issn = {00958956},
url = {https://linkinghub.elsevier.com/retrieve/pii/0095895674900677},
doi = {10.1016/0095-8956(74)90067-7},
number = {3},
journal = {Journal of Combinatorial Theory, Series B},
author = {Woodall, D.R},
year = {1974},
month = jun,
pages = {227–228},
language = {en}
}
@article{Brualdi_1969,
title = {Comments on bases in dependence structures},
volume = {1},
issn = {0004-9727, 1755-1633},
url = {https://www.cambridge.org/core/product/identifier/S000497270004140X/type/journal_article},
doi = {10.1017/S000497270004140X},
number = {2},
journal = {Bulletin of the Australian Mathematical Society},
author = {Brualdi, Richard A.},
year = {1969},
month = aug,
pages = {161–167},
language = {en}
}
@article{Asche_1966,
title = {Minimal dependent sets},
volume = {6},
issn = {0004-9735},
url = {https://www.cambridge.org/core/product/identifier/S1446788700004250/type/journal_article},
doi = {10.1017/S1446788700004250},
abstractnote = {The subject matter of this note is the notion of a dependence structure on an abstract set. There are a number of different approaches to this topic and it is known that many of these lead to precisely the same structure. Axioms are given here to specify the minimal dependent sets for such a structure. They are closely related to conditions introduced by Hassler Whitney in [1] and to a certain “elimination axiom” for the independent sets.},
number = {3},
journal = {Journal of the Australian Mathematical Society},
author = {Asche, D. S.},
year = {1966},
month = aug,
pages = {259–262},
language = {en}
}
@article{Greene_Magnanti_1975,
title = {Some Abstract Pivot Algorithms},
volume = {29},
issn = {0036-1399, 1095-712X},
url = {http://epubs.siam.org/doi/10.1137/0129045},
doi = {10.1137/0129045},
number = {3},
journal = {SIAM Journal on Applied Mathematics},
author = {Greene, Curtis and Magnanti, Thomas L.},
year = {1975},
month = nov,
pages = {530–539},
language = {en}
}
@incollection{Whiteley_matroids_1996,
address = {Providence, Rhode Island},
title = {Some matroids from discrete applied geometry},
volume = {197},
isbn = {978-0-8218-0508-4 978-0-8218-7788-3},
url = {http://www.ams.org/conm/197/},
abstract = {We present an array of matroids drawn from three sources in discrete applied geometry: (i) static (or first-order) rigidity of frameworks and higher skeletal rigidity; (ii) parallel drawings (or equivalently polyhedral pictures); and (iii) Crr−1-cofactors abstracted from multivariate splines in all dimensions. The strong analogies (sometimes isomorphisms) between generic rigidity matroids and generic cofactor matroids is one central theme of the chapter. We emphasize matroidal results for the combinatorial ‘generic’ situations, with geometric techniques used when they contribute combinatorial insights. A second basic theme is the analysis of represented matroids using the duality of row and column dependencies of the representing matrix (generalizing statics and kinematics in rigidity).},
language = {en},
urldate = {2024-06-11},
booktitle = {Contemporary {Mathematics}},
publisher = {American Mathematical Society},
author = {Whiteley, Walter},
editor = {Bonin, Joseph E. and Oxley, James G. and Servatius, Brigitte},
year = {1996},
doi = {10.1090/conm/197/02540},
pages = {171--311},
file = {Whiteley - 1996 - Some matroids from discrete applied geometry.pdf:/Users/congyu/Zotero/storage/VG5DFCBQ/Whiteley - 1996 - Some matroids from discrete applied geometry.pdf:application/pdf},
}
@article{crapo_higher_1967,
title = {A higher invariant for matroids},
volume = {2},
issn = {0021-9800},
url = {https://www.sciencedirect.com/science/article/pii/S0021980067800516},
doi = {10.1016/S0021-9800(67)80051-6},
abstract = {The Möbius invariant μ, essential to the classification of surfaces, is less useful in the study of exchange geometries (matroids) because it undergoes sizeable fluctuations as a result of minor structural changes, such as the lengthening of an arc. The number β, investigated here, is not only a geometric invariant, like μ, but is also a duality invariant, and provides a complete determination of separability.},
number = {4},
urldate = {2024-11-26},
journal = {Journal of Combinatorial Theory},
author = {Crapo, Henry H.},
month = jun,
year = {1967},
pages = {406--417},
file = {ScienceDirect Full Text PDF:/Users/congyu/Zotero/storage/P89DVYI9/Crapo - 1967 - A higher invariant for matroids.pdf:application/pdf;ScienceDirect Snapshot:/Users/congyu/Zotero/storage/IQL7L5TN/S0021980067800516.html:text/html},
}