1 Search Results for "Mao, Dejun"

Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2020.31
PACE Solver Description: Computing Exact Treedepth via Minimal Separators

Authors: Zijian Xu, Dejun Mao, and Vorapong Suppakitpaisarn

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
This is a description of team xuzijian629’s treedepth solver submitted to PACE 2020. As we use a top-down approach, we enumerate all possible minimal separators at each step. The enumeration is sped up by several novel pruning techniques and is based on our conjecture that we can always have an optimal decomposition without using separators with size larger than treewidth. Although we cannot theoretically guarantee that our algorithm based on the unproved conjecture can always give an optimal solution, it can give optimal solutions for all instances in our experiments. The algorithm solved 68 private instances and placed 5th in the competition.
Cite as

Zijian Xu, Dejun Mao, and Vorapong Suppakitpaisarn. PACE Solver Description: Computing Exact Treedepth via Minimal Separators. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 31:1-31:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{xu_et_al:LIPIcs.IPEC.2020.31,
  author =	{Xu, Zijian and Mao, Dejun and Suppakitpaisarn, Vorapong},
  title =	{{PACE Solver Description: Computing Exact Treedepth via Minimal Separators}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{31:1--31:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.31},
  URN =		{urn:nbn:de:0030-drops-133340},
  doi =		{10.4230/LIPIcs.IPEC.2020.31},
  annote =	{Keywords: Treedepth, Minimal Separators, Experimental Algorithm}
}
  • Refine by Author
  • 1 Mao, Dejun
  • 1 Suppakitpaisarn, Vorapong
  • 1 Xu, Zijian

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 1 Experimental Algorithm
  • 1 Minimal Separators
  • 1 Treedepth

  • Refine by Type
  • 1 document

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