Found 81 Documents (Results 1–81)
Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis. (English) Zbl 07883873
Uehara, Ryuhei (ed.) et al., WALCOM: algorithms and computation. 18th international conference and workshops on algorithms and computation, WALCOM 2024, Kanazawa, Japan, March 18–20, 2024. Proceedings. Singapore: Springer. Lect. Notes Comput. Sci. 14549, 242-256 (2024).
MSC:
68Wxx
Strengthening the directed Brooks’ theorem for oriented graphs and consequences on digraph redicolouring. (English) Zbl 1535.05113
Digraph redicolouring. (English) Zbl 1532.05076
Reviewer: V. Yegnanarayanan (Chennai)
Computational complexity of jumping block puzzles. (English) Zbl 07784207
MSC:
68Qxx
Recongo: bounded combinatorial reconfiguration with answer set programming. (English) Zbl 07855127
Gaggl, Sarah (ed.) et al., Logics in artificial intelligence. 18th European conference, JELIA 2023, Dresden, Germany, September 20–22, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14281, 278-286 (2023).
MSC:
68T27
Hamiltonian cycle reconfiguration with answer set programming. (English) Zbl 07855126
Gaggl, Sarah (ed.) et al., Logics in artificial intelligence. 18th European conference, JELIA 2023, Dresden, Germany, September 20–22, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14281, 262-277 (2023).
MSC:
68T27
Parameterized complexity of optimizing list vertex-coloring through reconfiguration. (English) Zbl 07770299
Lin, Chun-Cheng (ed.) et al., WALCOM: algorithms and computation. 17th international conference and workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13973, 279-290 (2023).
MSC:
68Wxx
On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets. (English) Zbl 1531.05192
Reviewer: Doost Ali Mojdeh (Bābolsar)
Irredundance graphs. (English) Zbl 1498.05188
MSC:
05C60
Computational complexity of jumping block puzzles. (English) Zbl 07670500
Chen, Chi-Yeh (ed.) et al., Computing and combinatorics. 27th international conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13025, 655-667 (2021).
MSC:
68Rxx
Decremental optimization of vertex-coloring under the reconfiguration framework. (English) Zbl 07670476
Chen, Chi-Yeh (ed.) et al., Computing and combinatorics. 27th international conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13025, 355-366 (2021).
MSC:
68Rxx
TS-reconfiguration of dominating sets in circle and circular-arc graphs. (English) Zbl 07530228
Bampis, Evripidis (ed.) et al., Fundamentals of computation theory. 23rd international symposium, FCT 2021, Athens, Greece, September 12–15, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12867, 114-134 (2021).
MSC:
68Qxx
Shortest reconfiguration of sliding tokens on subclasses of interval graphs. (English) Zbl 1497.68399
Reconfiguration graph for vertex colourings of weakly chordal graphs. (English) Zbl 1432.05040
MSC:
05C15
Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect. (English) Zbl 1436.68133
Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles. (English) Zbl 1429.05108
Reconfiguration graph for vertex colourings of weakly chordal graphs. (English) Zbl 07928512
MSC:
05C15
Linear transformations between colorings in chordal graphs. (English) Zbl 07525461
Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 24, 15 p. (2019).
MSC:
68Wxx
Diameter of colorings under Kempe changes. (English) Zbl 1456.05055
Du, Ding-Zhu (ed.) et al., Computing and combinatorics. 25th international conference, COCOON 2019, Xi’an, China, July 29–31, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11653, 52-64 (2019).
On \(k\)-total dominating graphs. (English) Zbl 1411.05196
MSC:
05C69
Connected \(k\)-dominating graphs. (English) Zbl 1400.05177
MSC:
05C69
Algorithms for coloring reconfiguration under recolorability constraints. (English) Zbl 1533.68262
Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 37, 13 p. (2018).
Distributed recoloring. (English) Zbl 1497.68369
Schmid, Ulrich (ed.) et al., 32nd international symposium on distributed computing, DISC 2018, New Orleans, Louisiana, USA, October 15–19, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 121, Article 12, 17 p. (2018).
Congestion-free rerouting of flows on DAGs. (English) Zbl 1499.68242
Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 143, 13 p. (2018).
Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs. (English) Zbl 1461.05092
Reconfiguration of graphs with connectivity constraints. (English) Zbl 1521.05088
Epstein, Leah (ed.) et al., Approximation and online algorithms. 16th international workshop, WAOA 2018, Helsinki, Finland, August 23–24, 2018. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 11312, 295-309 (2018).
Reviewer: Hang Lau (Montréal)
Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect. (English) Zbl 1436.68132
Wang, Lusheng (ed.) et al., Computing and combinatorics. 24th international conference, COCOON 2018, Qing Dao, China, July 2–4, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10976, 365-377 (2018).
Parameterized complexity of the list coloring reconfiguration problem with graph parameters. (English) Zbl 1395.68153
Complexity of coloring reconfiguration under recolorability constraints. (English) Zbl 1457.68224
Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 62, 12 p. (2017).
Parameterized complexity of the list coloring reconfiguration problem with graph parameters. (English) Zbl 1441.68109
Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 51, 13 p. (2017).
The coloring reconfiguration problem on specific graph classes. (English) Zbl 1470.05056
Gao, Xiaofeng (ed.) et al., Combinatorial optimization and applications. 11th international conference, COCOA 2017, Shanghai, China, December 16–18, 2017. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 10627, 152-162 (2017).
The connectivity of Boolean satisfiability: dichotomies for formulas and circuits. (English) Zbl 1378.68093
The complexity of (list) edge-coloring reconfiguration problem. (English) Zbl 1485.68195
Poon, Sheung-Hung (ed.) et al., WALCOM: algorithms and computation. 11th international conference and workshops, WALCOM 2017, Hsinchu, Taiwan, March 29–31, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10167, 347-358 (2017).
Kempe equivalence of colourings of cubic graphs. (English) Zbl 1348.05074
MSC:
05C15
A reconfigurations analogue of Brooks’ theorem and its consequences. (English) Zbl 1350.05034
MSC:
05C15
Classifying coloring graphs. (English) Zbl 1336.05040
MSC:
05C15
Kempe equivalence of colourings of cubic graphs. (English) Zbl 1346.05065
Nešetril, Jaroslav (ed.) et al., Extended abstracts of the eight European conference on combinatorics, graph theory and applications, EuroComb 2015, Bergen, Norway, August 31 – September 4, 2015. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 49, 243-249, electronic only (2015).
MSC:
05C15
Reconfiguration on sparse graphs. (English) Zbl 1451.68134
Dehne, Frank (ed.) et al., Algorithms and data structures. 14th international symposium, WADS 2015, Victoria, BC, Canada, August 5–7, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9214, 506-517 (2015).
Ground state connectivity of local Hamiltonians. (English) Zbl 1440.68097
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 617-628 (2015).
Degree-constrained subgraph reconfiguration is in P. (English) Zbl 1465.68108
Italiano, F. (ed.) et al., Mathematical foundations of computer science 2015. 40th international symposium, MFCS 2015, Milan, Italy, August 24–28, 2015. Proceedings. Part II. Berlin: Springer. Lect. Notes Comput. Sci. 9235, 505-516 (2015).
Finding shortest paths between graph colourings. (English) Zbl 1341.68062
Cygan, Marek (ed.) et al., Parameterized and exact computation. 9th international symposium, IPEC 2014, Wroclaw, Poland, September 10–12, 2014. Revised selected papers. Cham: Springer (ISBN 978-3-319-13523-6/pbk; 978-3-319-13524-3/ebook). Lecture Notes in Computer Science 8894, 221-233 (2014).
The \(k\)-dominating graph. (English) Zbl 1294.05122
MSC:
05C69
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. (English) Zbl 1284.05089
Filter Results by …
Document Type
- Journal Articles (58)
- Collection Articles (23)
all
top 5
Author
- Ito, Takehiro (11)
- Suzuki, Akira (10)
- Bousquet, Nicolas (9)
- Zhou, Xiao (9)
- Feghali, Carl (7)
- Johnson, Matthew (7)
- Paulusma, Daniël (7)
- Bonamy, Marthe (6)
- Brewster, Richard C. (5)
- Mouawad, Amer E. (5)
- Noel, Jonathan Andrew (5)
- Uehara, Ryuhei (5)
- Bonsma, Paul S. (4)
- Haas, Ruth (4)
- Heinrich, Marc (4)
- Lee, Jae-Baek (4)
- Nishimura, Naomi (4)
- Siggers, Mark H. (4)
- Wrochna, Marcin (4)
- Banbara, Mutsunori (3)
- Demaine, Erik D. (3)
- Hatanaka, Tatsuhiko (3)
- Inoue, Katsumi (3)
- Moore, Benjamin R. (3)
- Mühlenthaler, Moritz (3)
- Mynhardt, Christina Magdalena (3)
- Ono, Hirotaka (3)
- Osawa, Hiroki (3)
- Otachi, Yota (3)
- Patel, Viresh (3)
- Picasarri-Arrieta, Lucas (3)
- Schaub, Torsten H. (3)
- Asplund, John (2)
- Bartier, Valentin (2)
- Cardinal, Jean (2)
- Eppstein, David Arthur (2)
- Fiala, Jiří (2)
- Hearn, Robert A. (2)
- Kanzaki, Masaaki (2)
- Kobayashi, Yusuke (2)
- Kratsch, Dieter (2)
- Kratsch, Stefan (2)
- Lokshtanov, Daniel (2)
- Mizuta, Haruka (2)
- Nisse, Nicolas (2)
- Novick, Beth (2)
- Panolan, Fahad (2)
- Ramanujan, M. S. (2)
- Russell, Heather M. (2)
- Saurabh, Saket (2)
- Tamura, Yuma (2)
- Wasa, Kunihiro (2)
- Werner, Brett M. (2)
- Winslow, Andrew (2)
- Yamada, Takeshi (2)
- Yamada, Yuya (2)
- Yanagisawa, Yusuke (2)
- Akhoondian, Amiri Saeed (1)
- Alikhani, Saeid (1)
- Beier, Julie (1)
- Bhakta, Prateek (1)
- Buckner, Benjamin Brett (1)
- Demaine, Martin L. (1)
- Dudycz, Szymon (1)
- Edoh, Kossi (1)
- Eiben, Eduard (1)
- Farquhar, Lauren (1)
- Fatehi, David (1)
- Fierson, Janet (1)
- Fox-Epstein, Eli (1)
- Garnero, Valentin (1)
- Gharibian, Sevag (1)
- Haddadan, Arash (1)
- Havet, Frédéric (1)
- Hirate, Takahiro (1)
- Hoàng Anh Đức (1)
- Hristova, Yulia (1)
- Joffard, Alice (1)
- Junosza-Szaniawski, Konstanty (1)
- Kamat, Vikram (1)
- Kawamura, Kazuto (1)
- Krehbiel, Sara (1)
- Liedloff, Mathieu (1)
- Lignos, Ioannis (1)
- Lu, Xiaonan (1)
- MacGillivray, Gary (1)
- Mary, Arnaud (1)
- McGuinness, Sean (1)
- Melville, Eileen (1)
- Mofidi, Alireza (1)
- Montealegre, Pedro (1)
- Nabeshima, Hidetomo (1)
- Ohsaka, Naoto (1)
- Ouvrard, Paul (1)
- Perarnau, Guillem (1)
- Poznanović, Svetlana (1)
- Rabie, Mikaël (1)
- Raman, Venkatesh (1)
- Reinald, Amadeus (1)
- Rzążewski, Paweł (1)
- and 18 more Authors
all
top 5
Serial
- Theor. Comput. Sci. (12)
- Discrete Math. (7)
- J. Graph Theory (7)
- Eur. J. Comb. (5)
- Discrete Appl. Math. (3)
- J. Comb. Theory, Ser. B (3)
- Graphs Comb. (3)
- J. Comput. Syst. Sci. (2)
- Algorithmica (2)
- SIAM J. Discrete Math. (2)
- Australas. J. Comb. (2)
- J. Comb. Optim. (2)
- Algorithms (Basel) (2)
- Acta Inf. (1)
- Acta Math. Univ. Comen., New Ser. (1)
- J. Algebr. Comb. (1)
- Electron. J. Comb. (1)
- Theory Comput. Syst. (1)
- Parallel Process. Lett. (1)