Search Results

Documents authored by Johnson, John S.

Found 15 Possible Name Variants:

Johnson, John S.

Document
DOI: 10.4230/OASIcs.CMN.2016.2
Trailer Brain: Neural and Behavioral Analysis of Social Issue Documentary Viewing with Low-Density EEG

Authors: Jason S. Sherwin, Corinne Brenner, and John S. Johnson

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract
The effects of social issue documentaries are diverse. In particular, monetary donations and advocacy on social media are behavioral effects with public consequences. Conversely, information-seeking about an issue is potentially done in private. We designed a combined free-viewing and rapid perceptual decision-making experiment to simulate a real scenario confronted by otherwise uninformed movie-viewers, i.e., to determine what degree of support they will lend to a film based on its trailer. For a cohort of subjects with active video-streaming (e.g., Netflix) and social media accounts (e.g., Facebook), we recorded electroencephalography (EEG) and behavioral responses to trailers of social issue documentaries. We examined EEG using reliable component analysis (RCA), finding reliability within subjects across multiple viewings and across subjects within a given viewing of the same trailer. We found this reliability both over EEG captured from whole-movie viewing, as well as over 5-second movie segments. Behavioral responses following trailer viewing were not consistent from first to second viewings. Rather, support choices both tended towards extremes of support/non-support and were made faster upon second viewing. We hypothesized a relationship between reliability behavioral metrics, finding credible evidence for it in this dataset. Finally, we found that we could suitably train a naive classifier to categorize production value and narrative voice ratings given to the viewed movies from RCA-based metrics alone. In sum, our results show that EEG components during free-viewing of social issue documentary trailers can provide a useful tool to investigate viewers' neural responses during viewing, when coupled with a post hoc behavioral decision-making paradigm. The possibility of this tool being used by producers and filmmakers is also discussed.
Cite as

Jason S. Sherwin, Corinne Brenner, and John S. Johnson. Trailer Brain: Neural and Behavioral Analysis of Social Issue Documentary Viewing with Low-Density EEG. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sherwin_et_al:OASIcs.CMN.2016.2,
  author =	{Sherwin, Jason S. and Brenner, Corinne and Johnson, John S.},
  title =	{{Trailer Brain: Neural and Behavioral Analysis of Social Issue Documentary Viewing with Low-Density EEG}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{2:1--2:21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.2},
  URN =		{urn:nbn:de:0030-drops-67034},
  doi =		{10.4230/OASIcs.CMN.2016.2},
  annote =	{Keywords: EEG, reliable components analysis, machine learning, documentary films}
}

Johnson, David S.

Document
DOI: 10.4230/DagRep.6.3.24
Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111)

Authors: Daniel Delling, Camil Demetrescu, David S. Johnson, and Jan Vitek

Published in: Dagstuhl Reports, Volume 6, Issue 3 (2016)

Abstract
This report documents the talks and discussions at the Dagstuhl seminar 16111 "Rethinking Experimental Methods in Computing". The seminar brought together researchers from several computer science communities, including algorithm engineering, programming languages, information retrieval, high-performance computing, operations research, performance analysis, embedded systems, distributed systems, and software engineering. The main goals of the seminar were building a network of experimentalists and fostering a culture of sound quantitative experiments in computing. During the seminar, groups of participants have worked on distilling useful resources based on the collective experience gained in different communities and on planning actions to promote sound experimental methods and reproducibility efforts.
Cite as

Daniel Delling, Camil Demetrescu, David S. Johnson, and Jan Vitek. Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111). In Dagstuhl Reports, Volume 6, Issue 3, pp. 24-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{delling_et_al:DagRep.6.3.24,
  author =	{Delling, Daniel and Demetrescu, Camil and Johnson, David S. and Vitek, Jan},
  title =	{{Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111)}},
  pages =	{24--43},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{3},
  editor =	{Delling, Daniel and Demetrescu, Camil and Johnson, David S. and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.3.24},
  URN =		{urn:nbn:de:0030-drops-61463},
  doi =		{10.4230/DagRep.6.3.24},
  annote =	{Keywords: Algorithms, Benchmarks, Data sets, Experiments, Repeatability, Reproducibility, Software Artifacts, Statistics}
}
Document
DOI: 10.4230/DagRep.3.9.169
Algorithm Engineering (Dagstuhl Seminar 13391)

Authors: Andrew V. Goldberg, Giuseppe F. Italiano, David S. Johnson, and Dorothea Wagner

Published in: Dagstuhl Reports, Volume 3, Issue 9 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13391 "Algorithm Engineering". The algorithm engineering approach consists of a cycle of algorithm design, analysis, implementation, and experimental evaluation, with the aim of bridging the gap between theory and practice in the area of algorithms. This cycle of phases is driven by falsifiable hypotheses validated by experiments. Moreover, real-world instances often have direct impact on this cycle since they often expose modeling and analysis shortcomings. Algorithm engineering touches other research areas such as algorithm theory, combinatorial optimization, computer architecture, parallel and distributed computing, high-performance computing, and operations research. Prominent success stories in algorithm engineering include the linear program solver CPLEX, the traveling salesman suite CONCORDE, speed-up techniques for shortest paths computation, for example, in route planning, as well as graph partitioning and the computation of Steiner trees. All these topics are driven by the need for efficient algorithms and libraries for problems that appear frequently in real-world applications. In the last fifteen years, this approach to algorithmic research has gained increasing attention. There is an ACM Journal on Experimental Algorithmics and several annual conferences (WAE/ESA applied track since 1997, Alenex since 1998, and WEA/SEA since 2001) and the series of DIMACS implementation challenges where people meet to compare implementations for a specific problem. From 2007 to 2013 the German Research Foundation also funded a special priority program on algorithm engineering (DFG SPP 1307).
Cite as

Andrew V. Goldberg, Giuseppe F. Italiano, David S. Johnson, and Dorothea Wagner. Algorithm Engineering (Dagstuhl Seminar 13391). In Dagstuhl Reports, Volume 3, Issue 9, pp. 169-189, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{goldberg_et_al:DagRep.3.9.169,
  author =	{Goldberg, Andrew V. and Italiano, Giuseppe F. and Johnson, David S. and Wagner, Dorothea},
  title =	{{Algorithm Engineering (Dagstuhl Seminar 13391)}},
  pages =	{169--189},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{9},
  editor =	{Goldberg, Andrew V. and Italiano, Giuseppe F. and Johnson, David S. and Wagner, Dorothea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.9.169},
  URN =		{urn:nbn:de:0030-drops-44214},
  doi =		{10.4230/DagRep.3.9.169},
  annote =	{Keywords: Algorithm Engineering, Science of Algorithmics, Manycore Algorithms, Certifying Algorithms, Web Search, Large Graphs}
}
Document
DOI: 10.4230/DagSemProc.10261.1
10261 Abstracts Collection – Algorithm Engineering

Authors: Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders

Published in: Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)

Abstract
From June 27 to July 2, the Dagstuhl Seminar 10261 ``Algorithm Engineering '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders. 10261 Abstracts Collection – Algorithm Engineering. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{italiano_et_al:DagSemProc.10261.1,
  author =	{Italiano, Giuseppe F. and Johnson, David S. and Mutzel, Petra and Sanders, Peter},
  title =	{{10261 Abstracts Collection – Algorithm Engineering}},
  booktitle =	{Algorithm Engineering},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10261},
  editor =	{Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.1},
  URN =		{urn:nbn:de:0030-drops-28179},
  doi =		{10.4230/DagSemProc.10261.1},
  annote =	{Keywords: Experimental algorithmics, Game theory, Parallel and distributed algorithms, Multi-core}
}
Document
DOI: 10.4230/DagSemProc.10261.2
10261 Executive Summary – Algorithm Engineering

Authors: Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders

Published in: Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)

Abstract
Algorithm engineering (AE) consists of the design, theoretical analysis, implementation, and experimental evaluation of algorithms, with the aim of bridging the gap between theory and practice in the area of algorithms. In the last decade, this approach to algorithmic research has gained increasing attention. The aim of this seminar was to bring together researchers with different backgrounds, e.g., from combinatorial optimization, algorithmic theory, and algorithm engineering, in order to strengthen and foster collaborations in the area of algorithm engineering and to identify key research directions for the future.
Cite as

Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders. 10261 Executive Summary – Algorithm Engineering. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{italiano_et_al:DagSemProc.10261.2,
  author =	{Italiano, Giuseppe F. and Johnson, David S. and Mutzel, Petra and Sanders, Peter},
  title =	{{10261 Executive Summary – Algorithm Engineering}},
  booktitle =	{Algorithm Engineering},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10261},
  editor =	{Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.2},
  URN =		{urn:nbn:de:0030-drops-27966},
  doi =		{10.4230/DagSemProc.10261.2},
  annote =	{Keywords: Experimental algorithmics, Game theory, Parallel and distributed algorithms, Multi-core}
}
Document
DOI: 10.4230/DagSemRep.346
The Travelling Salesman Problem (Dagstuhl Seminar 02261)

Authors: David S. Johnson, Jan Karel Lenstra, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

David S. Johnson, Jan Karel Lenstra, and Gerhard J. Woeginger. The Travelling Salesman Problem (Dagstuhl Seminar 02261). Dagstuhl Seminar Report 346, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2004)

Copy BibTex To Clipboard

@TechReport{johnson_et_al:DagSemRep.346,
  author =	{Johnson, David S. and Lenstra, Jan Karel and Woeginger, Gerhard J.},
  title =	{{The Travelling Salesman Problem (Dagstuhl Seminar 02261)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{2004},
  type = 	{Dagstuhl Seminar Report},
  number =	{346},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.346},
  URN =		{urn:nbn:de:0030-drops-152271},
  doi =		{10.4230/DagSemRep.346},
}

Johnson, Rob

Document
DOI: 10.4230/LIPIcs.ESA.2022.16
When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting

Authors: Arghya Bhattacharya, Abiyaz Chowdhury, Helen Xu, Rathish Das, Rezaul A. Chowdhury, Rob Johnson, Rishab Nithyanand, and Michael A. Bender

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Cache-adaptive algorithms are a class of algorithms that achieve optimal utilization of dynamically changing memory. These memory fluctuations are the norm in today’s multi-threaded shared-memory machines and time-sharing caches. Bender et al. [Bender et al., 2014] proved that many cache-oblivious algorithms are optimally cache-adaptive, but that some cache-oblivious algorithms can be relatively far from optimally cache-adaptive on worst-case memory fluctuations. This worst-case gap between cache obliviousness and cache adaptivity depends on a highly-structured, adversarial memory profile. Existing cache-adaptive analysis does not predict the relative performance of cache-oblivious and cache-adaptive algorithms on non-adversarial profiles. Does the worst-case gap appear in practice, or is it an artifact of an unrealistically powerful adversary? This paper sheds light on the question of whether cache-oblivious algorithms can effectively adapt to realistically fluctuating memory sizes; the paper focuses on matrix multiplication and sorting. The two matrix-multiplication algorithms in this paper are canonical examples of "(a, b, c)-regular" cache-oblivious algorithms, which underlie much of the existing theory on cache-adaptivity. Both algorithms have the same asymptotic I/O performance when the memory size remains fixed, but one is optimally cache-adaptive, and the other is not. In our experiments, we generate both adversarial and non-adversarial memory workloads. The performance gap between the algorithms for matrix multiplication grows with problem size (up to 3.8×) on the adversarial profiles, but the gap does not grow with problem size (stays at 2×) on non-adversarial profiles. The sorting algorithms in this paper are not "(a, b, c)-regular," but they have been well-studied in the classical external-memory model when the memory size does not fluctuate. The relative performance of a non-oblivious (cache-aware) sorting algorithm degrades with the problem size: it incurs up to 6 × the number of disk I/Os compared to an oblivious adaptive algorithm on both adversarial and non-adversarial profiles. To summarize, in all our experiments, the cache-oblivious matrix-multiplication and sorting algorithms that we tested empirically adapt well to memory fluctuations. We conjecture that cache-obliviousness will empirically help achieve adaptivity for other problems with similar structures.
Cite as

Arghya Bhattacharya, Abiyaz Chowdhury, Helen Xu, Rathish Das, Rezaul A. Chowdhury, Rob Johnson, Rishab Nithyanand, and Michael A. Bender. When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ESA.2022.16,
  author =	{Bhattacharya, Arghya and Chowdhury, Abiyaz and Xu, Helen and Das, Rathish and Chowdhury, Rezaul A. and Johnson, Rob and Nithyanand, Rishab and Bender, Michael A.},
  title =	{{When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.16},
  URN =		{urn:nbn:de:0030-drops-169543},
  doi =		{10.4230/LIPIcs.ESA.2022.16},
  annote =	{Keywords: Cache-adaptive algorithms, cache-oblivious algorithms}
}
Document
DOI: 10.4230/DagRep.9.3.39
Theoretical Foundations of Storage Systems (Dagstuhl Seminar 19111)

Authors: Martin Farach-Colton, Inge Li Gørtz, Rob Johnson, and Donald E. Porter

Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19111 "Theoretical Foundations of Storage Systems." This seminar brought together researchers from two distinct communities - algorithms researchers with an interest in external memory and systems researchers with an interest in storage - with the objective of improving the design of future storage systems.
Cite as

Martin Farach-Colton, Inge Li Gørtz, Rob Johnson, and Donald E. Porter. Theoretical Foundations of Storage Systems (Dagstuhl Seminar 19111). In Dagstuhl Reports, Volume 9, Issue 3, pp. 39-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{farachcolton_et_al:DagRep.9.3.39,
  author =	{Farach-Colton, Martin and G{\o}rtz, Inge Li and Johnson, Rob and Porter, Donald E.},
  title =	{{Theoretical Foundations of Storage Systems (Dagstuhl Seminar 19111)}},
  pages =	{39--51},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{3},
  editor =	{Farach-Colton, Martin and G{\o}rtz, Inge Li and Johnson, Rob and Porter, Donald E.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.39},
  URN =		{urn:nbn:de:0030-drops-112909},
  doi =		{10.4230/DagRep.9.3.39},
  annote =	{Keywords: Storage Systems, External Memory Algorithms}
}

Johnson, Matthew

Document
DOI: 10.4230/LIPIcs.SWAT.2024.29
Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs

Authors: Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut) is NP-complete on planar graphs of maximum degree 3. In contrast, for the unweighted version, NP-completeness is only known for planar graphs of maximum degree 11. In fact, the complexity of unweighted Edge Multiway Cut was open for graphs of maximum degree 3 for over twenty years. We prove that the unweighted version is NP-complete even for planar graphs of maximum degree 3. As weighted Edge Multiway Cut is polynomial-time solvable for graphs of maximum degree at most 2, we have now closed the complexity gap. We also prove that (unweighted) Node Multiway Cut (both with and without deletable terminals) is NP-complete for planar graphs of maximum degree 3. By combining our results with known results, we can apply two meta-classifications on graph containment from the literature. This yields full dichotomies for all three problems on H-topological-minor-free graphs and, should H be finite, on H-subgraph-free graphs as well. Previously, such dichotomies were only implied for H-minor-free graphs.
Cite as

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.SWAT.2024.29,
  author =	{Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan},
  title =	{{Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.29},
  URN =		{urn:nbn:de:0030-drops-200699},
  doi =		{10.4230/LIPIcs.SWAT.2024.29},
  annote =	{Keywords: multiway cut, planar subcubic graph, complexity dichotomy, graph containment}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.57
Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Authors: Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
For any finite set ℋ = {H_1,…,H_p} of graphs, a graph is ℋ-subgraph-free if it does not contain any of H_1,…,H_p as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity can be classified on classes of ℋ-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.
Cite as

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.MFCS.2023.57,
  author =	{Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan},
  title =	{{Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.57},
  URN =		{urn:nbn:de:0030-drops-185914},
  doi =		{10.4230/LIPIcs.MFCS.2023.57},
  annote =	{Keywords: forbidden subgraphs, independent feedback vertex set, treewidth}
}
Document
DOI: 10.4230/LIPIcs.CPM.2019.20
Finding a Small Number of Colourful Components

Authors: Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Abstract
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not necessarily proper) colouring c is colourful if no two vertices in any V_i have the same colour and every set V_i induces a connected graph. The Colourful Partition problem, introduced by Adamaszek and Popa, is to decide whether a coloured graph (G,c) has a colourful partition of size at most k. This problem is related to the Colourful Components problem, introduced by He, Liu and Zhao, which is to decide whether a graph can be modified into a graph whose connected components form a colourful partition by deleting at most p edges. Despite the similarities in their definitions, we show that Colourful Partition and Colourful Components may have different complexities for restricted instances. We tighten known NP-hardness results for both problems by closing a number of complexity gaps. In addition, we prove new hardness and tractability results for Colourful Partition. In particular, we prove that deciding whether a coloured graph (G,c) has a colourful partition of size 2 is NP-complete for coloured planar bipartite graphs of maximum degree 3 and path-width 3, but polynomial-time solvable for coloured graphs of treewidth 2. Rather than performing an ad hoc study, we use our classical complexity results to guide us in undertaking a thorough parameterized study of Colourful Partition. We show that this leads to suitable parameters for obtaining FPT results and moreover prove that Colourful Components and Colourful Partition may have different parameterized complexities, depending on the chosen parameter.
Cite as

Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette. Finding a Small Number of Colourful Components. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bulteau_et_al:LIPIcs.CPM.2019.20,
  author =	{Bulteau, Laurent and Dabrowski, Konrad K. and Fertin, Guillaume and Johnson, Matthew and Paulusma, Dani\"{e}l and Vialette, St\'{e}phane},
  title =	{{Finding a Small Number of Colourful Components}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.20},
  URN =		{urn:nbn:de:0030-drops-104914},
  doi =		{10.4230/LIPIcs.CPM.2019.20},
  annote =	{Keywords: Colourful component, colourful partition, tree, treewidth, vertex cover}
}
Document
DOI: 10.4230/OASIcs.ICCSW.2018.11
Harnessing AI For Research

Authors: Matthew Johnson

Published in: OASIcs, Volume 66, 2018 Imperial College Computing Student Workshop (ICCSW 2018)

Abstract
Artificial Intelligence is increasingly being used to both augment existing fields of research and open up new avenues of discovery. From quality control for imaging flow cytometry to computational musicology, modern AI is an exciting new tool for research and thus knowing how to engineer AI systems in a research context is a vital new skill for RSEs to acquire. In this talk, I will outline four different areas of AI: supervised learning, unsupervised learning, interactive learning, and Bayesian learning. For each of these approaches, I will discuss how they typically map to different research problems and explore best practices for RSEs via specific use cases. At the end of the talk, you will have received a high-level overview of AI technologies and their use in research, have seen some cool examples of how AI has been used in a wide range of research areas, and have a good sense of where to go to learn more.
Cite as

Matthew Johnson. Harnessing AI For Research. In 2018 Imperial College Computing Student Workshop (ICCSW 2018). Open Access Series in Informatics (OASIcs), Volume 66, p. 11:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{johnson:OASIcs.ICCSW.2018.11,
  author =	{Johnson, Matthew},
  title =	{{Harnessing AI For Research}},
  booktitle =	{2018 Imperial College Computing Student Workshop (ICCSW 2018)},
  pages =	{11:1--11:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-097-2},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{66},
  editor =	{Pirovano, Edoardo and Graversen, Eva},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2018.11},
  URN =		{urn:nbn:de:0030-drops-101922},
  doi =		{10.4230/OASIcs.ICCSW.2018.11},
  annote =	{Keywords: Artificial intelligence}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.63
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

Authors: Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, and Viktor Zamaraev

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if we require that they are independent; that is, what is the price of independence? If G has a vertex cover, feedback vertex set or odd cycle transversal that is an independent set, then we let, respectively, ivc(G), ifvs(G) or ioct(G) denote the minimum size of such a set. We investigate for which graphs H the values of ivc(G), ifvs(G) and ioct(G) are bounded in terms of vc(G), fvs(G) and oct(G), respectively, when the graph G belongs to the class of H-free graphs. We find complete classifications for vertex cover and feedback vertex set and an almost complete classification for odd cycle transversal (subject to three non-equivalent open cases).
Cite as

Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, and Viktor Zamaraev. On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dabrowski_et_al:LIPIcs.MFCS.2018.63,
  author =	{Dabrowski, Konrad K. and Johnson, Matthew and Paesani, Giacomo and Paulusma, Dani\"{e}l and Zamaraev, Viktor},
  title =	{{On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.63},
  URN =		{urn:nbn:de:0030-drops-96452},
  doi =		{10.4230/LIPIcs.MFCS.2018.63},
  annote =	{Keywords: vertex cover, feedback vertex set, odd cycle transversal, price of independence}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.16
Independent Feedback Vertex Set for P_5-free Graphs

Authors: Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k>=0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding if a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P_4-free graphs. We show that it remains in P for P_5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks if a graph has an independent odd cycle transversal of size at most k for a given integer k>=0.
Cite as

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent Feedback Vertex Set for P_5-free Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.ISAAC.2017.16,
  author =	{Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l},
  title =	{{Independent Feedback Vertex Set for P\underline5-free Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.16},
  URN =		{urn:nbn:de:0030-drops-82308},
  doi =		{10.4230/LIPIcs.ISAAC.2017.16},
  annote =	{Keywords: feedback vertex set, odd cycle transversal, independent set, H-free graph}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.70
Recognizing Graphs Close to Bipartite Graphs

Authors: Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We continue research into a well-studied family of problems that ask if the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We let G be the class of k-degenerate graphs. The problem is known to be polynomial-time solvable if k=0 (bipartite graphs) and NP-complete if k=1 (near-bipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomial-time solvability for graphs of diameter 2. We show that recognizing near-bipartite graphs of diameter 3 is NP-complete resolving their open problem. To answer another open problem, we consider graphs of maximum degree D on n vertices. We show how to find A and B in O(n) time for k=1 and D=3, and in O(n^2) time for k >= 2 and D >= 4. These results also provide an algorithmic version of a result of Catlin [JCTB, 1979] and enable us to complete the complexity classification of another problem: finding a path in the vertex colouring reconfiguration graph between two given k-colourings of a graph of bounded maximum degree.
Cite as

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Recognizing Graphs Close to Bipartite Graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.MFCS.2017.70,
  author =	{Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l},
  title =	{{Recognizing Graphs Close to Bipartite Graphs}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.70},
  URN =		{urn:nbn:de:0030-drops-80740},
  doi =		{10.4230/LIPIcs.MFCS.2017.70},
  annote =	{Keywords: degenerate graphs, near-bipartite graphs, reconfiguration graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.73
Clique-Width for Graph Classes Closed under Complementation

Authors: Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, and Viktor Zamaraev

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We initiate a systematic study into the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the |H|=1 case by classifying the boundedness of clique-width for every set H of self-complementary graphs. We then completely settle the |H|=2 case. In particular, we determine one new class of (H1, complement of H1)-free graphs of bounded clique-width (as a side effect, this leaves only six classes of (H1, H2)-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the |H|=2 case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for a set F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for ({H1, complement of H1} + F)-free graphs coincides with the one for the |H|=2 case if and only if F does not include the bull (the only non-empty self-complementary graphs on fewer than five vertices are P_1 and P_4, and P_4-free graphs have clique-width at most 2). Finally, we discuss the consequences of our results for COLOURING.
Cite as

Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, and Viktor Zamaraev. Clique-Width for Graph Classes Closed under Complementation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{blanche_et_al:LIPIcs.MFCS.2017.73,
  author =	{Blanch\'{e}, Alexandre and Dabrowski, Konrad K. and Johnson, Matthew and Lozin, Vadim V. and Paulusma, Dani\"{e}l and Zamaraev, Viktor},
  title =	{{Clique-Width for Graph Classes Closed under Complementation}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.73},
  URN =		{urn:nbn:de:0030-drops-80756},
  doi =		{10.4230/LIPIcs.MFCS.2017.73},
  annote =	{Keywords: clique-width, self-complementary graph, forbidden induced subgraph}
}

Johnson, W. Lewis

Document
DOI: 10.4230/DagSemProc.04121.1
04121 Abstracts Collection – Evaluating Embodied Conversational Agents

Authors: Zsofia Ruttkay, Elisabeth André, W. Lewis Johnson, and Catherine Pelachaud

Published in: Dagstuhl Seminar Proceedings, Volume 4121, Evaluating Embodied Conversational Agents (2006)

Abstract
From 14.03.04 to 19.03.04, the Dagstuhl Seminar 04121 ``Evaluating Embodied Conversational Agents'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Zsofia Ruttkay, Elisabeth André, W. Lewis Johnson, and Catherine Pelachaud. 04121 Abstracts Collection – Evaluating Embodied Conversational Agents. In Evaluating Embodied Conversational Agents. Dagstuhl Seminar Proceedings, Volume 4121, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ruttkay_et_al:DagSemProc.04121.1,
  author =	{Ruttkay, Zsofia and Andr\'{e}, Elisabeth and Johnson, W. Lewis and Pelachaud, Catherine},
  title =	{{04121 Abstracts Collection – Evaluating Embodied Conversational Agents}},
  booktitle =	{Evaluating Embodied Conversational Agents},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{4121},
  editor =	{Zsofia Ruttkay and Elisabeth Andr\'{e} and W. Lewis Johnson and Catherine Pelachaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04121.1},
  URN =		{urn:nbn:de:0030-drops-5015},
  doi =		{10.4230/DagSemProc.04121.1},
  annote =	{Keywords: Critical evaluation of some implemented EcAs, issues and framework for evaluation and design}
}

Johnson, Jamie

Document
DOI: 10.4230/DagSemProc.04351.10
Continued Radicals

Authors: Jamie Johnson and Tom Richmond

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract
A nested radical with terms $a_1, a_2, \ldots , a_N$ is an expression of form $\sqrt{a_N + \cdots + \sqrt{a_2 + \sqrt{a_1}}}$. The limit as $N$ approaches infinity of such an expression, if it exists, is called a continued radical. We consider the set of real numbers $S(M)$ representable as a continued radical whose terms $a_1, a_2, \ldots$ are all from a finite set $M$ of nonnegative real numbers. We give conditions on the set $M$ for $S(M)$ to be (a) an interval, and (b) homeomorphic to the Cantor set.
Cite as

Jamie Johnson and Tom Richmond. Continued Radicals. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:DagSemProc.04351.10,
  author =	{Johnson, Jamie and Richmond, Tom},
  title =	{{Continued Radicals}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.10},
  URN =		{urn:nbn:de:0030-drops-1286},
  doi =		{10.4230/DagSemProc.04351.10},
  annote =	{Keywords: Continued radical}
}

Johnson, Jim

Document
DOI: 10.4230/DagSemProc.06121.3
06121 Report: Break Out Session on Guaranteed Execution

Authors: Calton Pu, Jim Johnson, Rogerio de Lemos, Andreas Reuter, David Taylor, and Irfan Zakiuddin

Published in: Dagstuhl Seminar Proceedings, Volume 6121, Atomicity: A Unifying Concept in Computer Science (2006)

Abstract
The break out session discussed guaranteed properties during program execution. Using a workflow example application, we discussed several research topics that form part of the guaranteed properties, including declarative specifications, generation of workflow program, generation of invariant guards, automated failure analysis, automated repair, and automated reconfiguration of workflow.
Cite as

Calton Pu, Jim Johnson, Rogerio de Lemos, Andreas Reuter, David Taylor, and Irfan Zakiuddin. 06121 Report: Break Out Session on Guaranteed Execution. In Atomicity: A Unifying Concept in Computer Science. Dagstuhl Seminar Proceedings, Volume 6121, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{pu_et_al:DagSemProc.06121.3,
  author =	{Pu, Calton and Johnson, Jim and de Lemos, Rogerio and Reuter, Andreas and Taylor, David and Zakiuddin, Irfan},
  title =	{{06121 Report: Break Out Session on Guaranteed Execution}},
  booktitle =	{Atomicity: A Unifying Concept in Computer Science},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6121},
  editor =	{Clifford B. Jones and David Lomet and Alexander Romanovsky and Gerhard Weikum},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06121.3},
  URN =		{urn:nbn:de:0030-drops-6410},
  doi =		{10.4230/DagSemProc.06121.3},
  annote =	{Keywords: Guaranteed properties, declarative specifications, generation of workflow program, generation of invariant guards, automated failure analysis, automat}
}

Johnson, David

Document
DOI: 10.4230/DagSemRep.78
Counting Issues: Theory and Application (Dagstuhl Seminar 9349)

Authors: Peter Gritzmann, David Johnson, Victor Klee, and Christoph Meinel

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Peter Gritzmann, David Johnson, Victor Klee, and Christoph Meinel. Counting Issues: Theory and Application (Dagstuhl Seminar 9349). Dagstuhl Seminar Report 78, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1994)

Copy BibTex To Clipboard

@TechReport{gritzmann_et_al:DagSemRep.78,
  author =	{Gritzmann, Peter and Johnson, David and Klee, Victor and Meinel, Christoph},
  title =	{{Counting Issues: Theory and Application (Dagstuhl Seminar 9349)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1994},
  type = 	{Dagstuhl Seminar Report},
  number =	{78},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.78},
  URN =		{urn:nbn:de:0030-drops-149668},
  doi =		{10.4230/DagSemRep.78},
}

Johnson, Ralph

Document
DOI: 10.4230/DagSemRep.368
Program Analysis for Object-Oriented Evolution (Dagstuhl Seminar 03091)

Authors: Ralph Johnson, Gregor Snelting, and Frank Tip

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Ralph Johnson, Gregor Snelting, and Frank Tip. Program Analysis for Object-Oriented Evolution (Dagstuhl Seminar 03091). Dagstuhl Seminar Report 368, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{johnson_et_al:DagSemRep.368,
  author =	{Johnson, Ralph and Snelting, Gregor and Tip, Frank},
  title =	{{Program Analysis for Object-Oriented Evolution (Dagstuhl Seminar 03091)}},
  pages =	{1--5},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{368},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.368},
  URN =		{urn:nbn:de:0030-drops-152481},
  doi =		{10.4230/DagSemRep.368},
}

Johnson, Christopher R.

Document
DOI: 10.4230/DagRep.12.8.1
Visualization and Decision Making Design Under Uncertainty (Dagstuhl Seminar 22331)

Authors: Nadia Boukhelifa, Christopher R. Johnson, and Kristi Potter

Published in: Dagstuhl Reports, Volume 12, Issue 8 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22331 "Visualization and Decision Making Design Under Uncertainty". The seminar brought together 33 researchers and practitioners from different domains concerned with visualization and decision making under uncertainty including visualization, visual analytics, human-computer interaction, artificial intelligence, climate research, geography and geology. The programme was organized in two parts: In the first part which lasted two days, participants gave short talks where they discussed current practices and the uncertainty visualization challenges they encountered in their own research. At the end of day two, participants brainstormed collectively around the main uncertainty visualization research challenges across domains and applications. In the second part, participants voted for the following three main challenges they wished to discuss for the remainder of the seminar (one and a half days): applications, human-centered uncertainty visualization, a design process for uncertainty visualization. Thus three break-out groups were formed to discuss these challenges. Abstracts for the individual talks and the break-out group activities are included in this report.
Cite as

Nadia Boukhelifa, Christopher R. Johnson, and Kristi Potter. Visualization and Decision Making Design Under Uncertainty (Dagstuhl Seminar 22331). In Dagstuhl Reports, Volume 12, Issue 8, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{boukhelifa_et_al:DagRep.12.8.1,
  author =	{Boukhelifa, Nadia and Johnson, Christopher R. and Potter, Kristi},
  title =	{{Visualization and Decision Making Design Under Uncertainty (Dagstuhl Seminar 22331)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{8},
  editor =	{Boukhelifa, Nadia and Johnson, Christopher R. and Potter, Kristi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.8.1},
  URN =		{urn:nbn:de:0030-drops-177120},
  doi =		{10.4230/DagRep.12.8.1},
  annote =	{Keywords: Decision making, Uncertainty visualization, Visual Analytics, Visualization}
}
Document
DOI: 10.4230/DagSemRep.370
Challenges in High Performance Simulations for Science and Engineering (Dagstuhl Seminar 03111)

Authors: Friedel Hoßfeld, Christopher R. Johnson, Hans Petter, and Unlrich Rüde

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Friedel Hoßfeld, Christopher R. Johnson, Hans Petter, and Unlrich Rüde. Challenges in High Performance Simulations for Science and Engineering (Dagstuhl Seminar 03111). Dagstuhl Seminar Report 370, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{hofeld_et_al:DagSemRep.370,
  author =	{Ho{\ss}feld, Friedel and Johnson, Christopher R. and Petter, Hans and R\"{u}de, Unlrich},
  title =	{{Challenges in High Performance Simulations for Science and Engineering (Dagstuhl Seminar 03111)}},
  pages =	{1--5},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{370},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.370},
  URN =		{urn:nbn:de:0030-drops-152509},
  doi =		{10.4230/DagSemRep.370},
}

Johnson, Marianne

Document
DOI: 10.4230/LIPIcs.MFCS.2017.48
The Shortest Identities for Max-Plus Automata with Two States

Authors: Laure Daviaud and Marianne Johnson

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Max-plus automata are quantitative extensions of automata designed to associate an integer with every non-empty word. A pair of distinct words is said to be an identity for a class of max-plus automata if each of the automata in the class computes the same value on the two words. We give the shortest identities holding for the class of max-plus automata with two states. For this, we exhibit an interesting list of necessary conditions for an identity to hold. Moreover, this result provides a counter-example of a conjecture of Izhakian, concerning the minimality of certain identities.
Cite as

Laure Daviaud and Marianne Johnson. The Shortest Identities for Max-Plus Automata with Two States. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{daviaud_et_al:LIPIcs.MFCS.2017.48,
  author =	{Daviaud, Laure and Johnson, Marianne},
  title =	{{The Shortest Identities for Max-Plus Automata with Two States}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.48},
  URN =		{urn:nbn:de:0030-drops-81048},
  doi =		{10.4230/LIPIcs.MFCS.2017.48},
  annote =	{Keywords: Max-plus automata, Weighted automata, Identities, Tropical matrices}
}

Johnson, Timothy

Document
DOI: 10.4230/LIPIcs.FUN.2021.4
Taming the Knight’s Tour: Minimizing Turns and Crossings

Authors: Juan Jose Besa, Timothy Johnson, Nil Mamano, and Martha C. Osegueda

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We introduce two new metrics of "simplicity" for knight’s tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.5n+O(1) turns and 13n+O(1) crossings on a n× n board, and we show lower bounds of (6-ε)n and 4n-O(1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 19/12+o(1) and 13/4+o(1). We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1,4)-leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases.
Cite as

Juan Jose Besa, Timothy Johnson, Nil Mamano, and Martha C. Osegueda. Taming the Knight’s Tour: Minimizing Turns and Crossings. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{besa_et_al:LIPIcs.FUN.2021.4,
  author =	{Besa, Juan Jose and Johnson, Timothy and Mamano, Nil and Osegueda, Martha C.},
  title =	{{Taming the Knight’s Tour: Minimizing Turns and Crossings}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.4},
  URN =		{urn:nbn:de:0030-drops-127654},
  doi =		{10.4230/LIPIcs.FUN.2021.4},
  annote =	{Keywords: Graph Drawing, Chess, Hamiltonian Cycle, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.81
Optimally Sorting Evolving Data

Authors: Juan Jose Besa, William E. Devanny, David Eppstein, Michael T. Goodrich, and Timothy Johnson

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of producing a final output, an algorithm attempts to maintain an output close to the correct output for the current state of the data, repeatedly updating its best estimate of a correct output over time. We show that a simple repeated insertion-sort algorithm can maintain an O(n) Kendall tau distance, with high probability, between a maintained list and an underlying total order of n items in an evolving data model where each comparison is followed by a swap between a random consecutive pair of items in the underlying total order. This result is asymptotically optimal, since there is an Omega(n) lower bound for Kendall tau distance for this problem. Our result closes the gap between this lower bound and the previous best algorithm for this problem, which maintains a Kendall tau distance of O(n log log n) with high probability. It also confirms previous experimental results that suggested that insertion sort tends to perform better than quicksort in practice.
Cite as

Juan Jose Besa, William E. Devanny, David Eppstein, Michael T. Goodrich, and Timothy Johnson. Optimally Sorting Evolving Data. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{besa_et_al:LIPIcs.ICALP.2018.81,
  author =	{Besa, Juan Jose and Devanny, William E. and Eppstein, David and Goodrich, Michael T. and Johnson, Timothy},
  title =	{{Optimally Sorting Evolving Data}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{81:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.81},
  URN =		{urn:nbn:de:0030-drops-90858},
  doi =		{10.4230/LIPIcs.ICALP.2018.81},
  annote =	{Keywords: Sorting, Evolving data, Insertion sort}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.24
Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs

Authors: Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
A square-contact representation of a planar graph G = (V,E) maps vertices in V to interior-disjoint axis-aligned squares in the plane and edges in E to adjacencies between the sides of the corresponding squares. In this paper, we study proper square-contact representations of planar graphs, in which any two squares are either disjoint or share infinitely many points. We characterize the partial 2-trees and the triconnected cycle-trees allowing for such representations. For partial 2-trees our characterization uses a simple forbidden subgraph whose structure forces a separating triangle in any embedding. For the triconnected cycle-trees, a subclass of the triconnected simply-nested graphs, we use a new structural decomposition for the graphs in this family, which may be of independent interest. Finally, we study square-contact representations of general triconnected simply-nested graphs with respect to their outerplanarity index.
Cite as

Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson. Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2017.24,
  author =	{Da Lozzo, Giordano and Devanny, William E. and Eppstein, David and Johnson, Timothy},
  title =	{{Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.24},
  URN =		{urn:nbn:de:0030-drops-82675},
  doi =		{10.4230/LIPIcs.ISAAC.2017.24},
  annote =	{Keywords: Square-Contact Representations, Partial 2-Trees, Simply-Nested Graphs}
}

Johnson, Daniel D.

Document
Multimedia Exposition
DOI: 10.4230/LIPIcs.SoCG.2018.75
Geometric Realizations of the 3D Associahedron (Multimedia Exposition)

Authors: Satyan L. Devadoss, Daniel D. Johnson, Justin Lee, and Jackson Warley

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
The associahedron is a convex polytope whose 1-skeleton is isomorphic to the flip graph of a convex polygon. There exists an elegant geometric realization of the associahedron, using the remarkable theory of secondary polytopes, based on the geometry of the underlying polygon. We present an interactive application that visualizes this correspondence in the 3D case.
Cite as

Satyan L. Devadoss, Daniel D. Johnson, Justin Lee, and Jackson Warley. Geometric Realizations of the 3D Associahedron (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 75:1-75:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{devadoss_et_al:LIPIcs.SoCG.2018.75,
  author =	{Devadoss, Satyan L. and Johnson, Daniel D. and Lee, Justin and Warley, Jackson},
  title =	{{Geometric Realizations of the 3D Associahedron}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{75:1--75:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.75},
  URN =		{urn:nbn:de:0030-drops-87886},
  doi =		{10.4230/LIPIcs.SoCG.2018.75},
  annote =	{Keywords: associahedron, secondary polytope, realization}
}

Johnson, Matthew P.

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.12
Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete

Authors: Matthew P. Johnson

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Interpreting three-leaf binary trees or rooted triples as constraints yields an entailment relation, whereby binary trees satisfying some rooted triples must also thus satisfy others, and thence a closure operator, which is known to be polynomial-time computable. This is extended to inconsistent triple sets by defining that a triple is entailed by such a set if it is entailed by any consistent subset of it. Determining whether the closure of an inconsistent rooted triple set can be computed in polynomial time was posed as an open problem in the Isaac Newton Institute's "Phylogenetics" program in 2007. It appears (as NC4) in a collection of such open problems maintained by Mike Steel, and it is the last of that collection's five problems concerning computational complexity to have remained open. We resolve the complexity of computing this closure, proving that its decision version is NP-Complete. In the process, we also prove that detecting the existence of any acyclic B-hyperpath (from specified source to destination) is NP-Complete, in a significantly narrower special case than the version whose minimization problem was recently proven NP-hard by Ritz et al. This implies it is NP-hard to approximate (our special case of) their minimization problem to within any factor.
Cite as

Matthew P. Johnson. Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{johnson:LIPIcs.ISAAC.2018.12,
  author =	{Johnson, Matthew P.},
  title =	{{Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{12:1--12:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.12},
  URN =		{urn:nbn:de:0030-drops-99600},
  doi =		{10.4230/LIPIcs.ISAAC.2018.12},
  annote =	{Keywords: phylogenetic trees, rooted triple entailment, NP-Completeness, directed hypergraphs, acyclic induced subgraphs, computational complexity}
}

Johnson, Robert F.

Document
DOI: 10.4230/LIPIcs.DNA.2020.2
Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks

Authors: Robert F. Johnson and Lulu Qian

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)

Abstract
In molecular programming, the Chemical Reaction Network model is often used to describe real or hypothetical systems. Often, an interesting computational task can be done with a known hypothetical Chemical Reaction Network, but often such networks have no known physical implementation. One of the important breakthroughs in the field was that any Chemical Reaction Network can be physically implemented, approximately, using DNA strand displacement mechanisms. This allows us to treat the Chemical Reaction Network model as a programming language and the implementation schemes as its compiler. This also suggests that it would be useful to optimize the result of such a compilation, and in general to find effective ways to design better DNA strand displacement systems. We discuss DNA strand displacement systems in terms of "motifs", short sequences of elementary DNA strand displacement reactions. We argue that describing such motifs in terms of their inputs and outputs, then building larger systems out of the abstracted motifs, can be an efficient way of designing DNA strand displacement systems. We discuss four previously studied motifs in this abstracted way, and present a new motif based on cooperative 4-way strand exchange. We then show how Chemical Reaction Network implementations can be built out of abstracted motifs, discussing existing implementations as well as presenting two new implementations based on 4-way strand exchange, one of which uses the new cooperative motif. The new implementations both have two desirable properties not found in existing implementations, namely both use only at most 2-stranded DNA complexes for signal and fuel complexes and both are physically reversible. There are reasons to believe that those properties may make them more robust and energy-efficient, but at the expense of using more fuel complexes than existing implementation schemes.
Cite as

Robert F. Johnson and Lulu Qian. Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.DNA.2020.2,
  author =	{Johnson, Robert F. and Qian, Lulu},
  title =	{{Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.2},
  URN =		{urn:nbn:de:0030-drops-129557},
  doi =		{10.4230/LIPIcs.DNA.2020.2},
  annote =	{Keywords: Molecular programming, DNA computing, Chemical Reaction Networks, DNA strand displacement}
}
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