2 Search Results for "Yen, Hsu-Chun"

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.29
A Dichotomy Result for Cyclic-Order Traversing Games

Authors: Yen-Ting Chen, Meng-Tsung Tsai, and Shi-Chun Tsai

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

Abstract
Traversing game is a two-person game played on a connected undirected simple graph with a source node and a destination node. A pebble is placed on the source node initially and then moves autonomously according to some rules. Alice is the player who wants to set up rules for each node to determine where to forward the pebble while the pebble reaches the node, so that the pebble can reach the destination node. Bob is the second player who tries to deter Alice's effort by removing edges. Given access to Alice's rules, Bob can remove as many edges as he likes, while retaining the source and destination nodes connected. Under the guide of Alice's rules, if the pebble arrives at the destination node, then we say Alice wins the traversing game; otherwise the pebble enters an endless loop without passing through the destination node, then Bob wins. We assume that Alice and Bob both play optimally. We study the problem: When will Alice have a winning strategy? This actually models a routing recovery problem in Software Defined Networking in which some links may be broken. In this paper, we prove a dichotomy result for certain traversing games, called cyclic-order traversing games. We also give a linear-time algorithm to find the corresponding winning strategy, if one exists.
Cite as

Yen-Ting Chen, Meng-Tsung Tsai, and Shi-Chun Tsai. A Dichotomy Result for Cyclic-Order Traversing Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2018.29,
  author =	{Chen, Yen-Ting and Tsai, Meng-Tsung and Tsai, Shi-Chun},
  title =	{{A Dichotomy Result for Cyclic-Order Traversing Games}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{29:1--29: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.29},
  URN =		{urn:nbn:de:0030-drops-99775},
  doi =		{10.4230/LIPIcs.ISAAC.2018.29},
  annote =	{Keywords: st-planar graphs, biconnectivity, fault-tolerant routing algorithms, software defined network}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.29
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}
}
  • Refine by Author
  • 1 Chang, Yi-Jun
  • 1 Chen, Yen-Ting
  • 1 Tsai, Meng-Tsung
  • 1 Tsai, Shi-Chun
  • 1 Yen, Hsu-Chun

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Networks → Network reliability
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Bend minimization
  • 1 biconnectivity
  • 1 fault-tolerant routing algorithms
  • 1 graph drawing
  • 1 orthogonal drawing
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2018

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