Tibor Jordán
Research Subjects
Tibor Jordán has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Bill Jackson
School of Mathematical Sciences Queen Mary University of London Mile End Road E1 4NS London United Kingdom
7 shared publications - Alex R. Berg
BRICS (Basic Research in Computer Science, Centre of the Danish National Research Foundation), University Of Aarhus, Aabogade 34 8200 Aarhus N, Denmark
3 shared publications - Viktoria E. Kaszanitzky
Department of Mathematics and Statistics Lancaster University LA1 4YF Lancaster United
2 shared publications Alex R. Berg
University of Aarhus
1 shared publication- András Frank
MTA-ELTE Egerváry Research Group, Department of Operations Research, Eötvös University, Budapest H-1117, Hungary
1 shared publication András Mihálykó
Eötvös University
1 shared publication
Latest Publications
- 29 May 2020
- Published by Springer Nature
- Vol. 12126, 330-342
The Steiner Problem for Count Matroids
We introduce and study a generalization of the well-known Steiner tree problem to count matroids. In the count matroid \(\mathcal{M}_{k,l}(G)\), defined on the edge set of a graph \(G=(V,E)\), a set \(F\subseteq E\) is independent if every vertex set \(X\subseteq V\) spans at most \(k|X|-l\) edges of F. The graph is called (k, l)-tight if its edge set is independent in \(\mathcal{M}_{k,l}(G)\) and \(|E|=k|V|-l\) holds. Given a graph \(G=(V,E)\), a non-negative length function \(w:E\rightarrow \mathbb {R}\), a set \(T\subseteq V\) of terminals and parameters k, l, our goal is to find a shortest (k, l)-tight subgraph of G that contains the terminals. Since \(\mathcal{M}_{1,1}(G)\) is isomorphic to the graphic matroid of G, the special case \(k=l=1\) corresponds to the Steiner tree problem. We obtain other interesting problems by choosing different parameters: for example, in the case \(k=2\), \(l=3\) the target is a shortest rigid subgraph containing all terminals. First we show that this problem is NP-hard even if \(k=2\), \(l=3\), and w is metric, or \(w\equiv 1\) and \(|T|=2\). As a by-product of this result we obtain that finding a shortest circuit in \(\mathcal{M}_{2,3}(G)\) is NP-hard. Then we design a \((k+1)\)-approximation algorithm for the metric version of the problem with parameters \((k,k+1)\), for all \(k\ge 2\). In particular, we obtain a 3-approximation algorithm for the Steiner version of the shortest rigid subgraph problem. We also show that the metric version can be solved in polynomial time for \(k=2\), \(l=3\), provided |T| is fixed.- 29 May 2020
- Published by Springer Nature
- Vol. 12126, 330-342
The Steiner Problem for Count Matroids
We introduce and study a generalization of the well-known Steiner tree problem to count matroids. In the count matroid \(\mathcal{M}_{k,l}(G)\), defined on the edge set of a graph \(G=(V,E)\), a set \(F\subseteq E\) is independent if every vertex set \(X\subseteq V\) spans at most \(k|X|-l\) edges of F. The graph is called (k, l)-tight if its edge set is independent in \(\mathcal{M}_{k,l}(G)\) and \(|E|=k|V|-l\) holds. Given a graph \(G=(V,E)\), a non-negative length function \(w:E\rightarrow \mathbb {R}\), a set \(T\subseteq V\) of terminals and parameters k, l, our goal is to find a shortest (k, l)-tight subgraph of G that contains the terminals. Since \(\mathcal{M}_{1,1}(G)\) is isomorphic to the graphic matroid of G, the special case \(k=l=1\) corresponds to the Steiner tree problem. We obtain other interesting problems by choosing different parameters: for example, in the case \(k=2\), \(l=3\) the target is a shortest rigid subgraph containing all terminals. First we show that this problem is NP-hard even if \(k=2\), \(l=3\), and w is metric, or \(w\equiv 1\) and \(|T|=2\). As a by-product of this result we obtain that finding a shortest circuit in \(\mathcal{M}_{2,3}(G)\) is NP-hard. Then we design a \((k+1)\)-approximation algorithm for the metric version of the problem with parameters \((k,k+1)\), for all \(k\ge 2\). In particular, we obtain a 3-approximation algorithm for the Steiner version of the shortest rigid subgraph problem. We also show that the metric version can be solved in polynomial time for \(k=2\), \(l=3\), provided |T| is fixed.- Open Access
- 28 April 2016
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 10 (2)
On universally rigid frameworks on the line
A $d$-dimensional bar-and-joint framework $(G,p)$ with underlying graph $G$ is called universally rigid if all realizations of $G$ with the same edge lengths, in all dimensions, are congruent to $(G,p)$. We give a complete characterization of universally rigid one-dimensional bar-and-joint frameworks in general position with a complete bipartite underlying graph. We show that the only bipartite graph for which all generic $d$-dimensional realizations are universally rigid is the complete graph on two vertices, for all $d\geq 1$. We also discuss several open questions concerning generically universally rigid graphs and the universal rigidity of general frameworks on the line.- 28 April 2016
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 10 (2)
Open AccessOn universally rigid frameworks on the line
A $d$-dimensional bar-and-joint framework $(G,p)$ with underlying graph $G$ is called universally rigid if all realizations of $G$ with the same edge lengths, in all dimensions, are congruent to $(G,p)$. We give a complete characterization of universally rigid one-dimensional bar-and-joint frameworks in general position with a complete bipartite underlying graph. We show that the only bipartite graph for which all generic $d$-dimensional realizations are universally rigid is the complete graph on two vertices, for all $d\geq 1$. We also discuss several open questions concerning generically universally rigid graphs and the universal rigidity of general frameworks on the line. - Open Access
- 1 February 2016
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 55 (2) , 314-372
Gain-Sparsity and Symmetry-Forced Rigidity in the Plane
We consider planar bar-and-joint frameworks with discrete point group symmetry in which the joint positions are as generic as possible subject to the symmetry constraint. We provide combinatorial characterizations for symmetry-forced rigidity of such structures with rotation symmetry or dihedral symmetry of order 2k with odd k, unifying and extending previous work on this subject. We also explore the matroidal background of our results and show that the matroids induced by the row independence of the orbit matrices of the symmetric frameworks are isomorphic to gain sparsity matroids defined on the quotient graph of the framework, whose edges are labeled by elements of the corresponding symmetry group. The proofs are based on new Henneberg type inductive constructions of the gain graphs that correspond to the bases of the matroids in question, which can also be seen as symmetry preserving graph operations in the original graph.
- 1 February 2016
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 55 (2) , 314-372
Open AccessGain-Sparsity and Symmetry-Forced Rigidity in the Plane
We consider planar bar-and-joint frameworks with discrete point group symmetry in which the joint positions are as generic as possible subject to the symmetry constraint. We provide combinatorial characterizations for symmetry-forced rigidity of such structures with rotation symmetry or dihedral symmetry of order 2k with odd k, unifying and extending previous work on this subject. We also explore the matroidal background of our results and show that the matroids induced by the row independence of the orbit matrices of the symmetric frameworks are isomorphic to gain sparsity matroids defined on the quotient graph of the framework, whose edges are labeled by elements of the corresponding symmetry group. The proofs are based on new Henneberg type inductive constructions of the gain graphs that correspond to the bases of the matroids in question, which can also be seen as symmetry preserving graph operations in the original graph.
- 9 September 2014
- Published by Springer Nature in Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry
- Vol. 56 (2) , 587-591
Henneberg moves on mechanisms
- 9 September 2014
- Published by Springer Nature in Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry
- Vol. 56 (2) , 587-591
Henneberg moves on mechanisms
- 1 May 2014
- Published by Elsevier in Discrete Optimization
- Vol. 12, 121-128
Orientations and detachments of graphs with prescribed degrees and connectivity
- 1 May 2014
- Published by Elsevier in Discrete Optimization
- Vol. 12, 121-128
Orientations and detachments of graphs with prescribed degrees and connectivity
- 4 January 2014
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 31 (3) , 585-599
Rigid Two-Dimensional Frameworks with Two Coincident Points
- 4 January 2014
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 31 (3) , 585-599
Rigid Two-Dimensional Frameworks with Two Coincident Points
- 31 August 2013
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 50 (3) , 537-551
Robust Tensegrity Polygons
- 31 August 2013
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 50 (3) , 537-551
Robust Tensegrity Polygons
- 1 May 2013
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 161 (7-8) , 1147-1149
Strongly rigid tensegrity graphs on the line
- 1 May 2013
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 161 (7-8) , 1147-1149
Strongly rigid tensegrity graphs on the line
- 1 January 2010
- Published by Springer Nature
- p. 151-172
Rigid and Globally Rigid Graphs with Pinned Vertices
- 1 January 2010
- Published by Springer Nature
- p. 151-172
Rigid and Globally Rigid Graphs with Pinned Vertices