2 Search Results for "Sanders, William H."

Document
DOI: 10.4230/LIPIcs.ESA.2020.42
A Polynomial Kernel for Line Graph Deletion

Authors: Eduard Eiben and William Lochet

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f ∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some graph. We study the Line-Graph-Edge Deletion problem, which asks whether we can delete at most k edges from the input graph G such that the resulting graph is a line graph. More precisely, we give a polynomial kernel for Line-Graph-Edge Deletion with O(k⁵) vertices. This answers an open question posed by Falk Hüffner at Workshop on Kernels (WorKer) in 2013.
Cite as

Eduard Eiben and William Lochet. A Polynomial Kernel for Line Graph Deletion. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.ESA.2020.42,
  author =	{Eiben, Eduard and Lochet, William},
  title =	{{A Polynomial Kernel for Line Graph Deletion}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.42},
  URN =		{urn:nbn:de:0030-drops-129088},
  doi =		{10.4230/LIPIcs.ESA.2020.42},
  annote =	{Keywords: Kernelization, line graphs, H-free editing, graph modification problem}
}
Document
DOI: 10.4230/DagRep.4.1.36
Randomized Timed and Hybrid Models for Critical Infrastructures (Dagstuhl Seminar 14031)

Authors: Erika Ábrahám, Alberto Avritzer, Anne Remke, and William H. Sanders

Published in: Dagstuhl Reports, Volume 4, Issue 1 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14031 "Randomized Timed and Hybrid Models for Critical Infrastructures". Critical Infrastructures, such as power grid and water and gas distribution networks, are essential for the functioning of our society and economy. Randomized Timed and Hybrid Models appear as a natural choice for their modeling, and come with existing algorithms and tool support for their analysis. However, on the one hand, the Critical Infrastructures community does not yet make full use of recent advances for Randomized Timed and Hybrid Models. On the other hand, existing algorithms are not yet readily applicable to the special kind of problems arising in Critical Infrastructures. This seminar brought together researchers from these fields to communicate with each other and to exchange knowledge, experiences and needs.
Cite as

Erika Ábrahám, Alberto Avritzer, Anne Remke, and William H. Sanders. Randomized Timed and Hybrid Models for Critical Infrastructures (Dagstuhl Seminar 14031). In Dagstuhl Reports, Volume 4, Issue 1, pp. 36-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{abraham_et_al:DagRep.4.1.36,
  author =	{\'{A}brah\'{a}m, Erika and Avritzer, Alberto and Remke, Anne and Sanders, William H.},
  title =	{{Randomized Timed and Hybrid Models for Critical Infrastructures (Dagstuhl Seminar 14031)}},
  pages =	{36--82},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{1},
  editor =	{\'{A}brah\'{a}m, Erika and Avritzer, Alberto and Remke, Anne and Sanders, William H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.1.36},
  URN =		{urn:nbn:de:0030-drops-45355},
  doi =		{10.4230/DagRep.4.1.36},
  annote =	{Keywords: Critical Infrastructures, Smart Grids, Modeling, Randomized Timed and Hybrid Models, Analysis}
}
  • Refine by Author
  • 1 Avritzer, Alberto
  • 1 Eiben, Eduard
  • 1 Lochet, William
  • 1 Remke, Anne
  • 1 Sanders, William H.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Analysis
  • 1 Critical Infrastructures
  • 1 H-free editing
  • 1 Kernelization
  • 1 Modeling
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2014
  • 1 2020

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