Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries. Matching Cuts in Graphs of High Girth and H-Free Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 31:1-31:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{feghali_et_al:LIPIcs.ISAAC.2023.31, author = {Feghali, Carl and Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard}, title = {{Matching Cuts in Graphs of High Girth and H-Free Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.31}, URN = {urn:nbn:de:0030-drops-193332}, doi = {10.4230/LIPIcs.ISAAC.2023.31}, annote = {Keywords: matching cut, perfect matching, girth, H-free graph} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Hoang-Oanh Le and Van Bang Le. Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 68:1-68:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{le_et_al:LIPIcs.MFCS.2022.68, author = {Le, Hoang-Oanh and Le, Van Bang}, title = {{Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {68:1--68:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.68}, URN = {urn:nbn:de:0030-drops-168663}, doi = {10.4230/LIPIcs.MFCS.2022.68}, annote = {Keywords: Cluster vertex deletion, Vertex cover, Computational complexity, Complexity dichotomy} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 37:1-37:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{golovach_et_al:LIPIcs.STACS.2021.37, author = {Golovach, Petr A. and Komusiewicz, Christian and Kratsch, Dieter and Le, Van Bang}, title = {{Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {37:1--37:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.37}, URN = {urn:nbn:de:0030-drops-136823}, doi = {10.4230/LIPIcs.STACS.2021.37}, annote = {Keywords: enumeration problems, polynomial delay, output-sensitive algorithms, kernelization, structural parameterizations, matching cuts} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Hoang-Oanh Le and Van Bang Le. Constrained Representations of Map Graphs and Half-Squares. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{le_et_al:LIPIcs.MFCS.2019.13, author = {Le, Hoang-Oanh and Le, Van Bang}, title = {{Constrained Representations of Map Graphs and Half-Squares}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {13:1--13:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.13}, URN = {urn:nbn:de:0030-drops-109574}, doi = {10.4230/LIPIcs.MFCS.2019.13}, annote = {Keywords: map graph, half-square, edge clique cover, edge clique partition, graph classes} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 19:1-19:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{komusiewicz_et_al:LIPIcs.IPEC.2018.19, author = {Komusiewicz, Christian and Kratsch, Dieter and Le, Van Bang}, title = {{Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.19}, URN = {urn:nbn:de:0030-drops-102207}, doi = {10.4230/LIPIcs.IPEC.2018.19}, annote = {Keywords: matching cut, decomposable graph, graph algorithm} }
Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Hoang-Oanh Le and Van Bang Le. On the Complexity of Matching Cut in Graphs of Fixed Diameter. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 50:1-50:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{le_et_al:LIPIcs.ISAAC.2016.50, author = {Le, Hoang-Oanh and Le, Van Bang}, title = {{On the Complexity of Matching Cut in Graphs of Fixed Diameter}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {50:1--50:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.50}, URN = {urn:nbn:de:0030-drops-68205}, doi = {10.4230/LIPIcs.ISAAC.2016.50}, annote = {Keywords: matching cut, NP-hardness, graph algorithm, computational complexity, decomposable graph} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Sudeshna Kolay and Fahad Panolan. Parameterized Algorithms for Deletion to (r,ell)-Graphs. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 420-433, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{kolay_et_al:LIPIcs.FSTTCS.2015.420, author = {Kolay, Sudeshna and Panolan, Fahad}, title = {{Parameterized Algorithms for Deletion to (r,ell)-Graphs}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {420--433}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.420}, URN = {urn:nbn:de:0030-drops-56456}, doi = {10.4230/LIPIcs.FSTTCS.2015.420}, annote = {Keywords: FPT, Turing kernels, Approximation algorithms} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Babak Farzad, Lap Chi Lau, Van Bang Le, and Nguyen Ngoc Tuy. Computing Graph Roots Without Short Cycles. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 397-408, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)
@InProceedings{farzad_et_al:LIPIcs.STACS.2009.1827, author = {Farzad, Babak and Lau, Lap Chi and Le, Van Bang and Tuy, Nguyen Ngoc}, title = {{Computing Graph Roots Without Short Cycles}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {397--408}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1827}, URN = {urn:nbn:de:0030-drops-18279}, doi = {10.4230/LIPIcs.STACS.2009.1827}, annote = {Keywords: Graph roots, Graph powers, Recognition algorithms, NP-completeness} }
Published in: Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007)
Van Bang Le and H.N. de Ridder. Linear-time certifying recognition for partitioned probe cographs. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2007)
@InProceedings{le_et_al:DagSemProc.07211.2, author = {Le, Van Bang and de Ridder, H.N.}, title = {{Linear-time certifying recognition for partitioned probe cographs}}, booktitle = {Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes}, pages = {1--4}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7211}, editor = {Andreas Brandst\"{a}dt and Klaus Jansen and Dieter Kratsch and Jeremy P. Spinrad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.2}, URN = {urn:nbn:de:0030-drops-12703}, doi = {10.4230/DagSemProc.07211.2}, annote = {Keywords: Cograph, probe cograph, certifying graph algorithm} }
Feedback for Dagstuhl Publishing