3 Search Results for "Schmidt, Nicolas"

Document
DOI: 10.4230/LIPIcs.CP.2022.23
Nucleus-Satellites Systems of OMDDs for Reducing the Size of Compiled Forms

Authors: Hélène Fargier, Jérôme Mengin, and Nicolas Schmidt

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
In order to reduce the size of compiled forms in knowledge compilation, we propose a new approach based on a splitting of the main representation into a nucleus representation and satellite representations. Nucleus representation is the projection of the original representation onto the "main" variables and satellite representations define the other variables according to the nucleus. We propose a language and a method, aimed at OBDD/OMDD representations, to compile into this split form. Our experimental study shows major size reductions on configuration- and diagnosis- oriented benchmarks.
Cite as

Hélène Fargier, Jérôme Mengin, and Nicolas Schmidt. Nucleus-Satellites Systems of OMDDs for Reducing the Size of Compiled Forms. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fargier_et_al:LIPIcs.CP.2022.23,
  author =	{Fargier, H\'{e}l\`{e}ne and Mengin, J\'{e}r\^{o}me and Schmidt, Nicolas},
  title =	{{Nucleus-Satellites Systems of OMDDs for Reducing the Size of Compiled Forms}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.23},
  URN =		{urn:nbn:de:0030-drops-166521},
  doi =		{10.4230/LIPIcs.CP.2022.23},
  annote =	{Keywords: Knowledge representation, knowledge compilation, ordered multivalued decision diagram}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.22
Local Certification of Graph Decompositions and Applications to Minor-Free Classes

Authors: Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph G belongs to a given graph class 𝒢. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this work, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds using a new proof technique.
Cite as

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.22,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o},
  title =	{{Local Certification of Graph Decompositions and Applications to Minor-Free Classes}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.22},
  URN =		{urn:nbn:de:0030-drops-157970},
  doi =		{10.4230/LIPIcs.OPODIS.2021.22},
  annote =	{Keywords: Local certification, proof-labeling schemes, locally checkable proofs, graph decompositions, minor-free graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.676
Computing 2-Walks in Polynomial Time

Authors: Andreas Schmid and Jens M. Schmidt

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions. We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.
Cite as

Andreas Schmid and Jens M. Schmidt. Computing 2-Walks in Polynomial Time. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 676-688, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{schmid_et_al:LIPIcs.STACS.2015.676,
  author =	{Schmid, Andreas and Schmidt, Jens M.},
  title =	{{Computing 2-Walks in Polynomial Time}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{676--688},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.676},
  URN =		{urn:nbn:de:0030-drops-49502},
  doi =		{10.4230/LIPIcs.STACS.2015.676},
  annote =	{Keywords: algorithms and data structures, 2-walks, 3-connected planar graphs, Tutte paths, 3-trees}
}
  • Refine by Author
  • 1 Bousquet, Nicolas
  • 1 Fargier, Hélène
  • 1 Feuilloley, Laurent
  • 1 Mengin, Jérôme
  • 1 Pierron, Théo
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Constraint and logic programming
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 2-walks
  • 1 3-connected planar graphs
  • 1 3-trees
  • 1 Knowledge representation
  • 1 Local certification
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2022
  • 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