3 Search Results for "Chang, Yen-Jung"


Document
On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs

Authors: Yi-Jun Chang and Hsu-Chun Yen

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


Abstract
An orthogonal drawing of a graph is a planar drawing where each edge is drawn as a sequence of horizontal and vertical line segments. Finding a bend-minimized orthogonal drawing of a planar graph of maximum degree 4 is NP-hard. The problem becomes tractable for planar graphs of maximum degree 3, and the fastest known algorithm takes O(n^5 log n) time. Whether a faster algorithm exists has been a long-standing open problem in graph drawing. In this paper we present an algorithm that takes only O~(n^{17/7}) time, which is a significant improvement over the previous state of the art.

Cite as

Yi-Jun Chang and Hsu-Chun Yen. On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.SoCG.2017.29,
  author =	{Chang, Yi-Jun and Yen, Hsu-Chun},
  title =	{{On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.29},
  URN =		{urn:nbn:de:0030-drops-72080},
  doi =		{10.4230/LIPIcs.SoCG.2017.29},
  annote =	{Keywords: Bend minimization, graph drawing, orthogonal drawing, planar graph}
}
Document
Predicate Detection for Parallel Computations with Locking Constraints

Authors: Yen-Jung Chang and Vijay K. Garg

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)


Abstract
The happened-before model (or the poset model) has been widely used for modeling the computations (execution traces) of parallel programs and detecting predicates (user-specified conditions). This model captures potential causality as well as locking constraints among the executed events of computations using Lamport's happened-before relation. The detection of a predicate in a computation is performed by checking if the predicate could become true in any reachable global state of the computation. In this paper, we argue that locking constraints are fundamentally different from potential causality. Hence, a poset is not an appropriate model for debugging purposes when the computations contain locking constraints. We present a model called Locking Poset, or a Loset, that generalizes the poset model for locking constraints. Just as a poset captures possibly an exponential number of total orders, a loset captures possibly an exponential number of posets. Therefore, detecting a predicate in a loset is equivalent to detecting the predicate in all corresponding posets. Since determining if a global state is reachable in a computation is a fundamental problem for detecting predicates, this paper first studies the reachability problem in the loset model. We show that the problem is NP-complete. Afterwards, we introduce a subset of reachable global states called lock-free feasible global states such that we can check whether a global state is lock-free feasible in polynomial time. Moreover, we show that lock-free feasible global states can act as "reset" points for reachability and be used to drastically reduce the time for determining the reachability of other global states. We also introduce strongly feasible global states that contain all reachable global states and show that the strong feasibility of a global state can be checked in polynomial time. We show that strong feasibility provides an effective approximation of reachability for many practical applications.

Cite as

Yen-Jung Chang and Vijay K. Garg. Predicate Detection for Parallel Computations with Locking Constraints. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.OPODIS.2016.17,
  author =	{Chang, Yen-Jung and Garg, Vijay K.},
  title =	{{Predicate Detection for Parallel Computations with Locking Constraints}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.17},
  URN =		{urn:nbn:de:0030-drops-70867},
  doi =		{10.4230/LIPIcs.OPODIS.2016.17},
  annote =	{Keywords: predicate detection, parallel computations, reachable global states, locking constraints, happened-before relation}
}
Document
QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations

Authors: Yen-Jung Chang and Vijay K. Garg

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)


Abstract
Verifying the correctness of executions of concurrent and distributed programs is difficult because they show nondeterministic behavior due to different process scheduling order. Predicate detection can alleviate this problem by predicting whether the user-specified condition (predicate) could have become true in any global state of the given concurrent or distributed computation. The method is predictive because it generates inferred global states from the observed execution path and then checks if those global states satisfy the predicate. An important part of the predicate detection method is global states enumeration, which generates the consistent global states, including the inferred ones, of the given computation. Cooper and Marzullo gave the first enumeration algorithm based on a breadth first strategy (BFS). Later, many algorithms have been proposed to improve the space and time complexity. Among the existing algorithms, the Tree algorithm due to Jegou et al. has the smallest time complexity and requires O(|P|) space, which is linear to the size of the computation P. In this paper, we present a fast algorithm, QuickLex, to enumerate global states in the lexical order. QuickLex requires much smaller space than O(|P|). From our experiments, the Tree algorithm requires 2-10 times more memory space than QuickLex. Moreover, QuickLex is 4 times faster than Tree even though the asymptotic time complexity of QuickLex is higher than that of Tree. The reason is that the worst case time complexity of QuickLex happens only in computations that are not common in practice. Moreover, Tree is built on linked-lists and QuickLex can be implemented using integer arrays. In comparison with the existing lexical algorithm (Lex), QuickLex is 7 times faster and uses almost the same amount of memory as Lex. Finally, we implement a parallel-and-online predicate detector for concurrent programs using QuickLex, which can detect data races and violation of invariants in the programs.

Cite as

Yen-Jung Chang and Vijay K. Garg. QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.OPODIS.2015.25,
  author =	{Chang, Yen-Jung and Garg, Vijay K.},
  title =	{{QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.25},
  URN =		{urn:nbn:de:0030-drops-66142},
  doi =		{10.4230/LIPIcs.OPODIS.2015.25},
  annote =	{Keywords: consistent global state, algorithm, computation}
}
  • Refine by Author
  • 2 Chang, Yen-Jung
  • 2 Garg, Vijay K.
  • 1 Chang, Yi-Jun
  • 1 Yen, Hsu-Chun

  • Refine by Classification

  • Refine by Keyword
  • 1 Bend minimization
  • 1 algorithm
  • 1 computation
  • 1 consistent global state
  • 1 graph drawing
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2017
  • 1 2016

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