2 Search Results for "Kaminski, Marcin"

Document
DOI: 10.4230/LIPIcs.STACS.2012.182
Contraction checking in graphs on surfaces

Authors: Marcin Kaminski and Dimitrios M. Thilikos

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

Abstract
The Contraction Checking problem asks, given two graphs H and G as input, whether H can be obtained from G by a sequence of edge contractions. Contraction Checking remains NP-complete, even when H is fixed. We show that this is not the case when G is embeddable in a surface of fixed Euler genus. In particular, we give an algorithm that solves Contraction Checking in f(h,g)*|V(G)|^3 steps, where h is the size of H and g is the Euler genus of the input graph G.
Cite as

Marcin Kaminski and Dimitrios M. Thilikos. Contraction checking in graphs on surfaces. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 182-193, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kaminski_et_al:LIPIcs.STACS.2012.182,
  author =	{Kaminski, Marcin and Thilikos, Dimitrios M.},
  title =	{{Contraction checking in graphs on surfaces}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{182--193},
  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.182},
  URN =		{urn:nbn:de:0030-drops-34032},
  doi =		{10.4230/LIPIcs.STACS.2012.182},
  annote =	{Keywords: Surfaces, Topological Minors, Contractions, Parameterized algorithms, Linkages}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2469
The k-in-a-path Problem for Claw-free Graphs

Authors: Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Testing whether there is an induced path in a graph spanning $k$ given vertices is already \NP-complete in general graphs when $k=3$. We show how to solve this problem in polynomial time on claw-free graphs, when $k$ is not part of the input but an arbitrarily fixed integer.
Cite as

Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma. The k-in-a-path Problem for Claw-free Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 371-382, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fiala_et_al:LIPIcs.STACS.2010.2469,
  author =	{Fiala, Jiri and Kaminski, Marcin and Lidick\'{y}, Bernard and Paulusma, Dani\"{e}l},
  title =	{{The k-in-a-path Problem for Claw-free Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{371--382},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, 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.2010.2469},
  URN =		{urn:nbn:de:0030-drops-24692},
  doi =		{10.4230/LIPIcs.STACS.2010.2469},
  annote =	{Keywords: Induced path, claw-free graph, polynomial-time algorithm}
}
  • Refine by Author
  • 2 Kaminski, Marcin
  • 1 Fiala, Jiri
  • 1 Lidický, Bernard
  • 1 Paulusma, Daniël
  • 1 Thilikos, Dimitrios M.

  • Refine by Classification

  • Refine by Keyword
  • 1 Contractions
  • 1 Induced path
  • 1 Linkages
  • 1 Parameterized algorithms
  • 1 Surfaces
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2010
  • 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