1 Search Results for "Bulian, Jannis"

Document
DOI: 10.4230/LIPIcs.IPEC.2015.236
Fixed-parameter Tractable Distances to Sparse Graph Classes

Authors: Jannis Bulian and Anuj Dawar

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We show that for various classes C of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph G to C is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is FPT. The second shows that determining the elimination distance of a graph G to a minor-closed class C is FPT.
Cite as

Jannis Bulian and Anuj Dawar. Fixed-parameter Tractable Distances to Sparse Graph Classes. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 236-247, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bulian_et_al:LIPIcs.IPEC.2015.236,
  author =	{Bulian, Jannis and Dawar, Anuj},
  title =	{{Fixed-parameter Tractable Distances to Sparse Graph Classes}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{236--247},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.236},
  URN =		{urn:nbn:de:0030-drops-55865},
  doi =		{10.4230/LIPIcs.IPEC.2015.236},
  annote =	{Keywords: parameterized complexity, fixed-parameter tractable, distance, graph theory, sparse graphs, graph minor, nowhere dense}
}
  • Refine by Author
  • 1 Bulian, Jannis
  • 1 Dawar, Anuj

  • Refine by Classification

  • Refine by Keyword
  • 1 distance
  • 1 fixed-parameter tractable
  • 1 graph minor
  • 1 graph theory
  • 1 nowhere dense
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

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