Source author record

Michael Gentner

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Robotics

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Active Visuo-Tactile Interactive Robotic Perception for Accurate Object Pose Estimation in Dense Clutter

This work presents a novel active visuo-tactile based framework for robotic systems to accurately estimate pose of objects in dense cluttered environments. The scene representation is derived using a novel declutter graph (DG) which describes the relationship among objects in the scene for decluttering by leveraging semantic segmentation and grasp affordances networks. The graph formulation allows robots to efficiently declutter the workspace by autonomously selecting the next best object to remove and the optimal action (prehensile or non-prehensile) to perform. Furthermore, we propose a novel translation-invariant Quaternion filter (TIQF) for active vision and active tactile based pose estimation. Both active visual and active tactile points are selected by maximizing the expected information gain. We evaluate our proposed framework on a system with two robots coordinating on randomized scenes of dense cluttered objects and perform ablation studies with static vision and active vision based estimation prior and post decluttering as baselines. Our proposed active visuo-tactile interactive perception framework shows upto 36% improvement in pose accuracy compared to the active vision baseline.

preprint2016arXiv

Dynamic Monopolies for Degree Proportional Thresholds in Connected Graphs of Girth at least Five and Trees

Let $G$ be a graph, and let $ρ\in (0,1)$ . For a set $D$ of vertices of $G$ , let the set $H_ρ(D)$ arise by starting with the set $D$ , and iteratively adding further vertices $u$ to the current set if they have at least $\lceil ρd_G(u)\rceil$ neighbors in it. If $H_ρ(D)$ contains all vertices of $G$ , then $D$ is known as an irreversible dynamic monopoly or a perfect target set associated with the threshold function $u\mapsto \lceil ρd_G(u)\rceil$ . Let $h_ρ(G)$ be the minimum cardinality of such an irreversible dynamic monopoly. For a connected graph $G$ of maximum degree at least $\frac{1}ρ$ , Chang (Triggering cascades on undirected connected graphs, Information Processing Letters 111 (2011) 973-978) showed $h_ρ(G)\leq 5.83ρn(G)$ , which was improved by Chang and Lyuu (Triggering cascades on strongly connected directed graphs, Theoretical Computer Science 593 (2015) 62-69) to $h_ρ(G)\leq 4.92ρn(G)$ . We show that for every $ε>0$ , there is some $ρ(ε)>0$ such that $h_ρ(G) \leq(2+ε)ρn(G)$ for every $ρ$ in $(0,ρ(ε))$ , and every connected graph $G$ that has maximum degree at least $\frac{1}ρ$ and girth at least $5$ . Furthermore, we show that $h_ρ(T) \leq ρn(T)$ for every $ρ$ in $(0,1]$ , and every tree $T$ that has order at least $\frac{1}ρ$ .

preprint2016arXiv

Large Values of the Clustering Coefficient

A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (Collective dynamics of `small-world' networks, Nature 393 (1998) 440-442), is the clustering coefficient of a graph $G$ . It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex $u$ of $G$ is the relative density $m(G[N_G(u)])/{d_G(u)\choose 2}$ of its neighborhood if $d_G(u)$ is at least $2$ , and $0$ otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size. We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge.

preprint2016arXiv

Some Bounds on the Zero Forcing Number of a Graph

A set $Z$ of vertices of a graph $G$ is a zero forcing set of $G$ if initially labeling all vertices in $Z$ with $1$ and all remaining vertices of $G$ with $0$ , and then, iteratively and as long as possible, changing the label of some vertex $u$ from $0$ to $1$ if $u$ is the only neighbor with label $0$ of some vertex with label $1$ , results in the entire vertex set of $G$ . The zero forcing number $Z(G)$ , defined as the minimum order of a zero forcing set of $G$ , was proposed as an upper bound of the corank of matrices associated with $G$ , and was also considered in connection with quantum physics and logic circuits. In view of the computational hardness of the zero forcing number, upper and lower bounds are of interest. Refining results of Amos, Caro, Davila, and Pepper, we show that $Z(G)\leq \frac{Δ-2}{Δ-1}n$ for a connected graph $G$ of order $n$ and maximum degree $Δ$ at least $3$ if and only if $G$ does not belong to $\{ K_{Δ+1},K_{Δ,Δ},K_{Δ-1,Δ},G_1,G_2\}$ , where $G_1$ and $G_2$ are two specific graphs of orders $5$ and $7$ , respectively. For a connected graph $G$ of order $n$ , maximum degree $3$ , and girth at least $5$ , we show $Z(G)\leq \frac{n}{2}-Ω\left(\frac{n}{\log n}\right)$ . Using a probabilistic argument, we show $Z(G)\leq \left(1-\frac{H_r}{r}+o\left(\frac{H_r}{r}\right)\right)n$ for an $r$ -regular graph $G$ of order $n$ and girth at least $5$ , where $H_r$ is the $r$ -th harmonic number. Finally, we show $Z(G)\geq (g-2)(δ-2)+2$ for a graph $G$ of girth $g\in \{ 5,6\}$ and minimum degree $δ$ , which partially confirms a conjecture of Davila and Kenter.

preprint2016arXiv

Some Comments on the Slater number

Let $G$ be a graph with degree sequence $d_1\geq \ldots \geq d_n$ . Slater proposed $s\ell(G)=\min\{ s: (d_1+1)+\cdots+(d_s+1)\geq n\}$ as a lower bound on the domination number $γ(G)$ of $G$ . We show that deciding the equality of $γ(G)$ and $s\ell(G)$ for a given graph $G$ is NP-complete but that one can decide efficiently whether $γ(G)>s\ell(G)$ or $γ(G)\leq \left(\left\lceil\ln \left(\frac{n(G)}{s\ell(G)}\right)\right\rceil+1\right)s\ell(G)$ . For real numbers $α$ and $β$ with $α\geq \max\{ 0,β\}$ , let ${\cal G}(α,β)$ be the class of non-null graphs $G$ such that every non-null subgraph $H$ of $G$ has at most $αn(H)-β$ many edges. Generalizing a result of Desormeaux, Haynes, and Henning, we show that $γ(G)\leq (2α+1)s\ell(G)-2β$ for every graph $G$ in ${\cal G}(α,β)$ with $α\leq \frac{3}{2}$ . Furthermore, we show that $γ(G)/s\ell(G)$ is bounded for graphs $G$ in ${\cal G}(α,β)$ if and only if $α<2$ . For an outerplanar graph $G$ with $s\ell(G)\geq 2$ , we show $γ(G)\leq 6s\ell(G)-6$ . In analogy to $s\ell(G)$ , we propose $s\ell_t(G)=\min\{ s: d_1+\cdots+d_s\geq n\}$ as a lower bound on the total domination number. Strengthening results due to Raczek as well as Chellali and Haynes, we show that $s\ell_t(T)\geq \frac{n+2-n_1}{2}$ for every tree $T$ of order $n$ at least $2$ with $n_1$ endvertices.

preprint2015arXiv

Independence in Uniform Linear Triangle-free Hypergraphs

The independence number $α(H)$ of a hypergraph $H$ is the maximum cardinality of a set of vertices of $H$ that does not contain an edge of $H$ . Generalizing Shearer's classical lower bound on the independence number of triangle-free graphs (J. Comb. Theory, Ser. B 53 (1991) 300-307), and considerably improving recent results of Li and Zang (SIAM J. Discrete Math. 20 (2006) 96-104) and Chishti et al. (Acta Univ. Sapientiae, Informatica 6 (2014) 132-158), we show that $α(H)\geq \sum_{u\in V(H)}f_r(d_H(u))$ for an $r$ -uniform linear triangle-free hypergraph $H$ with $r\geq 2$ , where \begin{eqnarray*} f_r(0)&=&1\mbox{, and }\\ f_r(d)&=&\frac{1+\Big((r-1)d^2-d\Big)f_r(d-1)}{1+(r-1)d^2}\mbox{ for $d\geq 1$ .} \end{eqnarray*}

preprint2015arXiv

Largest Domination Number and Smallest Independence Number of Forests with given Degree Sequence

For a sequence $d$ of non-negative integers, let ${\cal F}(d)$ be the set of all forests whose degree sequence is $d$ . We present closed formulas for $γ_{\max}^{\cal F}(d)=\max\{ γ(F):F\in {\cal F}(d)\}$ and $α_{\min}^{\cal F}(d)=\min\{ α(F):F\in {\cal F}(d)\}$ where $γ(F)$ and $α(F)$ are the domination number and the independence number of a forest $F$ , respectively.

preprint2015arXiv

Smallest Domination Number and Largest Independence Number of Graphs and Forests with given Degree Sequence

For a sequence $d$ of non-negative integers, let ${\cal G}(d)$ and ${\cal F}(d)$ be the sets of all graphs and forests with degree sequence $d$ , respectively. Let $γ_{\min}(d)=\min\{ γ(G):G\in {\cal G}(d)\}$ , $α_{\max}(d)=\max\{ α(G):G\in {\cal G}(d)\}$ , $γ_{\min}^{\cal F}(d)=\min\{ γ(F):F\in {\cal F}(d)\}$ , and $α_{\max}^{\cal F}(d)=\max\{ α(F):F\in {\cal F}(d)\}$ where $γ(G)$ is the domination number and $α(G)$ is the independence number of a graph $G$ . Adapting results of Havel and Hakimi, Rao showed in 1979 that $α_{\max}(d)$ can be determined in polynomial time. We establish the existence of realizations $G\in {\cal G}(d)$ with $γ_{\min}(d)=γ(G)$ , and $F_γ,F_α\in {\cal F}(d)$ with $γ_{\min}^{\cal F}(d)=γ(F_γ)$ and $α_{\max}^{\cal F}(d)=α(F_α)$ that have strong structural properties. This leads to an efficient algorithm to determine $γ_{\min}(d)$ for every given degree sequence $d$ with bounded entries as well as closed formulas for $γ_{\min}^{\cal F}(d)$ and $α_{\max}^{\cal F}(d)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Michael Gentner

Research overview

Is this your work?

8 publications

Active Visuo-Tactile Interactive Robotic Perception for Accurate Object Pose Estimation in Dense Clutter

Dynamic Monopolies for Degree Proportional Thresholds in Connected Graphs of Girth at least Five and Trees

Large Values of the Clustering Coefficient

Some Bounds on the Zero Forcing Number of a Graph

Some Comments on the Slater number

Independence in Uniform Linear Triangle-free Hypergraphs

Largest Domination Number and Smallest Independence Number of Forests with given Degree Sequence

Smallest Domination Number and Largest Independence Number of Graphs and Forests with given Degree Sequence

See the researcher in context

Building this map preview