Document

**Published in:** LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

We formalize the simplification of activity-on-edge graphs used for visualizing project schedules, where the vertices of the graphs represent project milestones, and the edges represent either tasks of the project or timing constraints between milestones. In this framework, a timeline of the project can be constructed as a leveled drawing of the graph, where the levels of the vertices represent the time at which each milestone is scheduled to happen. We focus on the following problem: given an activity-on-edge graph representing a project, find an equivalent activity-on-edge graph—one with the same critical paths—that has the minimum possible number of milestone vertices among all equivalent activity-on-edge graphs. We provide an O(mn²)-time algorithm for solving this graph minimization problem.

David Eppstein, Daniel Frishberg, and Elham Havvaei. Simplifying Activity-On-Edge Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.SWAT.2020.24, author = {Eppstein, David and Frishberg, Daniel and Havvaei, Elham}, title = {{Simplifying Activity-On-Edge Graphs}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.24}, URN = {urn:nbn:de:0030-drops-122718}, doi = {10.4230/LIPIcs.SWAT.2020.24}, annote = {Keywords: directed acyclic graph, activity-on-edge graph, critical path, project planning, milestone minimization, graph visualization} }

Document

**Published in:** LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

The k-leaf power graph G of a tree T is a graph whose vertices are the leaves of T and whose edges connect pairs of leaves at unweighted distance at most k in T. Recognition of the k-leaf power graphs for k >= 6 is still an open problem. In this paper, we provide an algorithm for this problem for sparse leaf power graphs. Our result shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by k and by the degeneracy of the given graph. To prove this, we describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of k and the degeneracy of G. As a result, we can use methods based on monadic second-order logic (MSO_2) to recognize the existence of a leaf power as a subgraph of the product graph.

David Eppstein and Elham Havvaei. Parameterized Leaf Power Recognition via Embedding into Graph Products. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.IPEC.2018.16, author = {Eppstein, David and Havvaei, Elham}, title = {{Parameterized Leaf Power Recognition via Embedding into Graph Products}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {16:1--16:14}, 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.16}, URN = {urn:nbn:de:0030-drops-102179}, doi = {10.4230/LIPIcs.IPEC.2018.16}, annote = {Keywords: leaf power, phylogenetic tree, monadic second-order logic, Courcelle's theorem, strong product of graphs, fixed-parameter tractability} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail