3 Search Results for "Kuhnert, J�rg"

Document
DOI: 10.4230/LIPIcs.IPEC.2017.2
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable

Authors: Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these, called Isomorphism With Restrictions, is to decide for two given graphs X_1=(V,E_1) and X_2=(V,E_2) and a subset R\subseteq V\times V of forbidden pairs whether there is an isomorphism \pi from X_1 to X_2 such that i^\pi\ne j for all (i,j)\in R. We prove that this problem and several of its generalizations are in fact in \FPT: - The problem of deciding whether there is an isomorphism between two graphs that moves k vertices and satisfies Lubiw-style constraints is in FPT, with k and the size of R as parameters. The problem remains in FPT even if a conjunction of disjunctions of such constraints is allowed. As a consequence of the main result it follows that the problem to decide whether there is an isomorphism that moves exactly k vertices is in FPT. This solves a question left open in our article on exact weight automorphisms [STACS 2017]. - When the number of moved vertices is unrestricted, finding isomorphisms that satisfy a CNF of Lubiw-style constraints can be solved in FPT with access to a GI oracle. - Checking if there is an isomorphism π between two graphs with complexity t is also in FPT with t as parameter, where the complexity of a permutation is the Cayley measure defined as the minimum number t such that \pi can be expressed as a product of t transpositions. - We consider a more general problem in which the vertex set of a graph X is partitioned into Red and Blue, and we are interested in an automorphism that stabilizes Red and Blue and moves exactly k vertices in Blue, where k is the parameter. This problem was introduced by [Downey and Fellows 1999], and we showed [STACS 2017] that it is W[1]-hard even with color classes of size 4 inside Red. Now, for color classes of size at most 3 inside Red, we show the problem is in FPT. In the non-parameterized setting, all these problems are NP-complete. Also, they all generalize in several ways the problem to decide whether there is an isomorphism between two graphs that moves at most k vertices, shown to be in FPT by Schweitzer [ESA 2011].
Cite as

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.IPEC.2017.2,
  author =	{Arvind, Vikraman and K\"{o}bler, Johannes and Kuhnert, Sebastian and Tor\'{a}n, Jacobo},
  title =	{{Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.2},
  URN =		{urn:nbn:de:0030-drops-85690},
  doi =		{10.4230/LIPIcs.IPEC.2017.2},
  annote =	{Keywords: parameterized algorithms, hypergraph isomorphism, mislabeled graphs}
}
Document
DOI: 10.4230/DFU.Vol2.SciViz.2011.260
Generation of Adaptive Streak Surfaces Using Moving Least Squares

Authors: Harald Obermaier, Martin Hering-Bertram, Jörg Kuhnert, and Hans Hagen

Published in: Dagstuhl Follow-Ups, Volume 2, Scientific Visualization: Interactions, Features, Metaphors (2011)

Abstract
We introduce a novel method for the generation of fully adaptive streak surfaces in time-varying flow fields based on particle advection and adaptive mesh refinement. Moving least squares approximation plays an important role in multiple stages of the proposed algorithm, which adaptively refines the surface based on curvature approximation and circumradius properties of the underlying Delaunay mesh. We utilize the grid-less Moving Least Squares approximation method for both curvature and surface estimation as well as vector field evaluation during particle advection. Delaunay properties of the surface triangulation are guaranteed by edge flipping operations on the progressive surface mesh. The results of this work illustrate the benefit of adaptivity techniques to streak surface generation and provide the means for a qualitative analysis of the presented approach.
Cite as

Harald Obermaier, Martin Hering-Bertram, Jörg Kuhnert, and Hans Hagen. Generation of Adaptive Streak Surfaces Using Moving Least Squares. In Scientific Visualization: Interactions, Features, Metaphors. Dagstuhl Follow-Ups, Volume 2, pp. 260-275, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InCollection{obermaier_et_al:DFU.Vol2.SciViz.2011.260,
  author =	{Obermaier, Harald and Hering-Bertram, Martin and Kuhnert, J\"{o}rg and Hagen, Hans},
  title =	{{Generation of Adaptive Streak Surfaces Using Moving Least Squares}},
  booktitle =	{Scientific Visualization: Interactions, Features, Metaphors},
  pages =	{260--275},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-26-2},
  ISSN =	{1868-8977},
  year =	{2011},
  volume =	{2},
  editor =	{Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol2.SciViz.2011.260},
  URN =		{urn:nbn:de:0030-drops-32982},
  doi =		{10.4230/DFU.Vol2.SciViz.2011.260},
  annote =	{Keywords: scattered, flow, streak surface, adaptivity, moving least squares}
}
Document
DOI: 10.4230/OASIcs.VLUDS.2010.55
On Moving Least Squares Based Flow Visualization

Authors: Harald Obermaier, Martin Hering-Bertram, Jörg Kuhnert, and Hans Hagen

Published in: OASIcs, Volume 19, Visualization of Large and Unstructured Data Sets - Applications in Geospatial Planning, Modeling and Engineering (IRTG 1131 Workshop) (2011)

Abstract
Modern simulation and measurement methods tend to produce meshfree data sets if modeling of processes or objects with free surfaces or boundaries is desired. In Computational Fluid Dynamics (CFD), such data sets are described by particle-based vector fields. This paper presents a summary of a selection of methods for the extraction of geometric features of such point-based vector fields while pointing out its challenges, limitations, and applications.
Cite as

Harald Obermaier, Martin Hering-Bertram, Jörg Kuhnert, and Hans Hagen. On Moving Least Squares Based Flow Visualization. In Visualization of Large and Unstructured Data Sets - Applications in Geospatial Planning, Modeling and Engineering (IRTG 1131 Workshop). Open Access Series in Informatics (OASIcs), Volume 19, pp. 55-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{obermaier_et_al:OASIcs.VLUDS.2010.55,
  author =	{Obermaier, Harald and Hering-Bertram, Martin and Kuhnert, J\"{o}rg and Hagen, Hans},
  title =	{{On Moving Least Squares Based Flow  Visualization}},
  booktitle =	{Visualization of Large and Unstructured Data Sets - Applications in Geospatial Planning, Modeling and Engineering (IRTG 1131 Workshop)},
  pages =	{55--63},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-29-3},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{19},
  editor =	{Middel, Ariane and Scheler, Inga and Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.VLUDS.2010.55},
  URN =		{urn:nbn:de:0030-drops-30979},
  doi =		{10.4230/OASIcs.VLUDS.2010.55},
  annote =	{Keywords: Moving Least Squares, Approximation, Flow, Scientific Visualization}
}
  • Refine by Author
  • 2 Hagen, Hans
  • 2 Hering-Bertram, Martin
  • 2 Kuhnert, Jörg
  • 2 Obermaier, Harald
  • 1 Arvind, Vikraman
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation
  • 1 Flow
  • 1 Moving Least Squares
  • 1 Scientific Visualization
  • 1 adaptivity
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2011
  • 1 2018

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