4 Search Results for "Davies, James"


Document
A Solution to Ringel’s Circle Problem

Authors: James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak

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


Abstract
We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to Ringel’s circle problem (1959). The proof relies on a (multidimensional) version of Gallai’s theorem with polynomial constraints, which we derive from the Hales-Jewett theorem and which may be of independent interest.

Cite as

James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak. A Solution to Ringel’s Circle Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.SoCG.2022.33,
  author =	{Davies, James and Keller, Chaya and Kleist, Linda and Smorodinsky, Shakhar and Walczak, Bartosz},
  title =	{{A Solution to Ringel’s Circle Problem}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{33:1--33: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.33},
  URN =		{urn:nbn:de:0030-drops-160413},
  doi =		{10.4230/LIPIcs.SoCG.2022.33},
  annote =	{Keywords: circle arrangement, chromatic number, Gallai’s theorem, polynomial method}
}
Document
Track A: Algorithms, Complexity and Games
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs

Authors: Ewan Davies and Will Perkins

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density α_c(Δ) and provide (i) for α < α_c(Δ) randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most α n in n-vertex graphs of maximum degree Δ; and (ii) a proof that unless NP=RP, no such algorithms exist for α > α_c(Δ). The critical density is the occupancy fraction of hard core model on the clique K_{Δ+1} at the uniqueness threshold on the infinite Δ-regular tree, giving α_c(Δ) ~ e/(1+e)1/(Δ) as Δ → ∞.

Cite as

Ewan Davies and Will Perkins. Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.ICALP.2021.62,
  author =	{Davies, Ewan and Perkins, Will},
  title =	{{Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{62:1--62:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.62},
  URN =		{urn:nbn:de:0030-drops-141310},
  doi =		{10.4230/LIPIcs.ICALP.2021.62},
  annote =	{Keywords: approximate counting, independent sets, Markov chains}
}
Document
Colouring Polygon Visibility Graphs and Their Generalizations

Authors: James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3⋅4^{ω-1}. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo-visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a colouring with the claimed number of colours can be computed in polynomial time.

Cite as

James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak. Colouring Polygon Visibility Graphs and Their Generalizations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.SoCG.2021.29,
  author =	{Davies, James and Krawczyk, Tomasz and McCarty, Rose and Walczak, Bartosz},
  title =	{{Colouring Polygon Visibility Graphs and Their Generalizations}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.29},
  URN =		{urn:nbn:de:0030-drops-138281},
  doi =		{10.4230/LIPIcs.SoCG.2021.29},
  annote =	{Keywords: Visibility graphs, \chi-boundedness, pseudoline arrangements, ordered graphs}
}
Document
Structured Audio Information Retrieval System

Authors: Dirk Schnelle and Frankie James

Published in: Dagstuhl Seminar Proceedings, Volume 5181, Mobile Computing and Ambient Intelligence: The Challenge of Multimedia (2005)


Abstract
The Structured Audio Information Retrieval System (STAIRS) project targets environments where workers need access to information, but cannot use traditional hands-and-eyes devices, such as a PDA. The information to be accessed is stored in an information base, either as pre-recorded audio or as text to be run through a text-to-speech engine. Given the inherent limitations of the simple audio interface used in STAIRS, it is important to structure the information base in a way which makes navigation as easy as possible for the user.

Cite as

Dirk Schnelle and Frankie James. Structured Audio Information Retrieval System. In Mobile Computing and Ambient Intelligence: The Challenge of Multimedia. Dagstuhl Seminar Proceedings, Volume 5181, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{schnelle_et_al:DagSemProc.05181.13,
  author =	{Schnelle, Dirk and James, Frankie},
  title =	{{Structured Audio Information Retrieval System}},
  booktitle =	{Mobile Computing and Ambient Intelligence: The Challenge of Multimedia},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5181},
  editor =	{Nigel Davies and Thomas Kirste and Heidrun Schumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05181.13},
  URN =		{urn:nbn:de:0030-drops-3700},
  doi =		{10.4230/DagSemProc.05181.13},
  annote =	{Keywords: STAIRS, mobile worker, hands and eyes free, audio, Voice user Interface}
}
  • Refine by Author
  • 2 Davies, James
  • 2 Walczak, Bartosz
  • 1 Davies, Ewan
  • 1 James, Frankie
  • 1 Keller, Chaya
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 Gallai’s theorem
  • 1 Markov chains
  • 1 STAIRS
  • 1 Visibility graphs
  • 1 Voice user Interface
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2021
  • 1 2005
  • 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