2 Search Results for "Mitsche, Dieter"

Document
DOI: 10.4230/LIPIcs.STACS.2012.408
On the treewidth and related parameters of random geometric graphs

Authors: Dieter Mitsche and Guillem Perarnau

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G(n,r) in [0,sqrt(n)]^2. More precisely, we show that there exists some c_1 > 0, such that for any constant 0 < r < c_1, tw(G)=Theta(log(n)/loglog(n)), and also, there exists some c_2 > c_1, such that for any r=r(n)> c_2, tw(G)=Theta(r sqrt(n)). Our proofs show that for the corresponding values of r the same asymptotic bounds also hold for the pathwidth and treedepth of a random geometric graph.
Cite as

Dieter Mitsche and Guillem Perarnau. On the treewidth and related parameters of random geometric graphs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 408-419, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{mitsche_et_al:LIPIcs.STACS.2012.408,
  author =	{Mitsche, Dieter and Perarnau, Guillem},
  title =	{{On the treewidth and related parameters of random geometric graphs}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{408--419},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.408},
  URN =		{urn:nbn:de:0030-drops-34280},
  doi =		{10.4230/LIPIcs.STACS.2012.408},
  annote =	{Keywords: Random geometric graphs, treewidth, treedepth}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1750
A new upper bound for 3-SAT

Authors: Josep Diaz, Lefteris Kirousis, Dieter Mitsche, and Xavier Perez-Gimenez

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
We show that a randomly chosen $3$-CNF formula over $n$ variables with clauses-to-variables ratio at least $4.4898$ is asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was $4.506$. The first such bound, independently discovered by many groups of researchers since 1983, was $5.19$. Several decreasing values between $5.19$ and $4.506$ were published in the years between. The probabilistic techniques we use for the proof are, we believe, of independent interest.
Cite as

Josep Diaz, Lefteris Kirousis, Dieter Mitsche, and Xavier Perez-Gimenez. A new upper bound for 3-SAT. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 163-174, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{diaz_et_al:LIPIcs.FSTTCS.2008.1750,
  author =	{Diaz, Josep and Kirousis, Lefteris and Mitsche, Dieter and Perez-Gimenez, Xavier},
  title =	{{A new upper bound for 3-SAT}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{163--174},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1750},
  URN =		{urn:nbn:de:0030-drops-17507},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1750},
  annote =	{Keywords: Satisfiability, 3-SAT, random, threshold}
}
  • Refine by Author
  • 2 Mitsche, Dieter
  • 1 Diaz, Josep
  • 1 Kirousis, Lefteris
  • 1 Perarnau, Guillem
  • 1 Perez-Gimenez, Xavier

  • Refine by Classification

  • Refine by Keyword
  • 1 3-SAT
  • 1 Random geometric graphs
  • 1 Satisfiability
  • 1 random
  • 1 threshold
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2012

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