2 Search Results for "Li, Ki-Joune"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.23
Precoloring Extension with Demands on Paths

Authors: Arun Kumar Das, Michal Opler, and Tomáš Valla

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.
Cite as

Arun Kumar Das, Michal Opler, and Tomáš Valla. Precoloring Extension with Demands on Paths. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2025.23,
  author =	{Das, Arun Kumar and Opler, Michal and Valla, Tom\'{a}\v{s}},
  title =	{{Precoloring Extension with Demands on Paths}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.23},
  URN =		{urn:nbn:de:0030-drops-249319},
  doi =		{10.4230/LIPIcs.ISAAC.2025.23},
  annote =	{Keywords: precoloring extension, distance coloring, FPT, approximation algorithms}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.21
Improved and More Complete Conceptual Model for the Revision of IndoorGML (Short Paper)

Authors: Abdullah Alattas, Sisi Zlatanova, Peter van Oosterom, and Ki-Joune Li

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
With the increasing number of indoor navigation applications, it is essential to have clear and complete conceptual model (in the form of UML class diagram) for IndoorGML. The current version of IndoorGML standard has an incomplete class diagram (incomplete w.r.t. attributes, of which some are appearing in the XML/GML schema), and that provides confusion for the users of the standard. Furthermore, there are some issues related to unclear association names, unclear class names, classes that related to the Primal space and the Dual space, code lists not specific per type (which should have their own code list values), untyped relationships to external object classes, and semantically overlapping classes. In this paper, we propose an enhancement for IndoorGML conceptual model (UML class diagram) to avoid the misunderstanding. We propose a conceptual model that maps the classes of the standard in a better way. This conceptual model is the basis for 1) a database schema when storing IndoorGML data, 2) the XML schema when exchanging IndoorGML data, and 3) when developing IndoorGML applications with an intuitive and clear GUI. Furthermore, the proposed conceptual model provides constraints for more meaningful model and to define more sharply what is considered valid data. This paper briefly reports these preliminary results on the UML conceptual model.
Cite as

Abdullah Alattas, Sisi Zlatanova, Peter van Oosterom, and Ki-Joune Li. Improved and More Complete Conceptual Model for the Revision of IndoorGML (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{alattas_et_al:LIPIcs.GISCIENCE.2018.21,
  author =	{Alattas, Abdullah and Zlatanova, Sisi and van Oosterom, Peter and Li, Ki-Joune},
  title =	{{Improved and More Complete Conceptual Model for the Revision of IndoorGML}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.21},
  URN =		{urn:nbn:de:0030-drops-93491},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.21},
  annote =	{Keywords: Navigation, Space, Boundary, CellSpace}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018

  • Refine by Author
  • 1 Alattas, Abdullah
  • 1 Das, Arun Kumar
  • 1 Li, Ki-Joune
  • 1 Opler, Michal
  • 1 Valla, Tomáš
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Information systems → Geographic information systems
  • 1 Information systems → Location based services
  • 1 Software and its engineering → Unified Modeling Language (UML)
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Boundary
  • 1 CellSpace
  • 1 FPT
  • 1 Navigation
  • 1 Space
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact