2 Search Results for "Lahiri, Abhiruk"

Document
DOI: 10.4230/LIPIcs.SoCG.2022.38
On Comparable Box Dimension

Authors: Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Two boxes in ℝ^d are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in ℝ^d. We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion.
Cite as

Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On Comparable Box Dimension. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.38,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Gon\c{c}alves, Daniel and Lahiri, Abhiruk and Tan, Jane and Ueckerdt, Torsten},
  title =	{{On Comparable Box Dimension}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.38},
  URN =		{urn:nbn:de:0030-drops-160461},
  doi =		{10.4230/LIPIcs.SoCG.2022.38},
  annote =	{Keywords: geometric graphs, minor-closed graph classes, treewidth fragility}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.40
Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs

Authors: Zdeněk Dvořák and Abhiruk Lahiri

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable on graphs of bounded treewidth. These schemes apply in all fractionally treewidth-fragile graph classes, a property which is true for many natural graph classes with sublinear separators. We also provide quasipolynomial-time approximation schemes for these problems in all classes with sublinear separators.
Cite as

Zdeněk Dvořák and Abhiruk Lahiri. Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 40:1-40:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ESA.2021.40,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Lahiri, Abhiruk},
  title =	{{Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{40:1--40:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.40},
  URN =		{urn:nbn:de:0030-drops-146216},
  doi =		{10.4230/LIPIcs.ESA.2021.40},
  annote =	{Keywords: approximation, sublinear separators}
}
  • Refine by Author
  • 2 Dvořák, Zdeněk
  • 2 Lahiri, Abhiruk
  • 1 Gonçalves, Daniel
  • 1 Tan, Jane
  • 1 Ueckerdt, Torsten

  • Refine by Classification
  • 1 Mathematics of computing → Graphs and surfaces
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 approximation
  • 1 geometric graphs
  • 1 minor-closed graph classes
  • 1 sublinear separators
  • 1 treewidth fragility

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact