Ken-ichi Kawarabayashi's PUBLISHED PAPERS
-
From the plane to higher surfaces,
(with C. Thomassen), J. Combin. Theory Ser. B 102 (2012), 852--868.
-
Fixed-parameter tractability for the
subset feedback set problem and the $S$-cycle packing problem (Y. Kobayashi),
J. Combin. Theory Ser. B 102 (2012), 1020--1034.
-
Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core,
(with T. Akiba and C. Sommer), EDBT 2012 - 15th International Conference on Extending Database Technology, 144--155.
-
Packing Cycles through Prescribed Vertices under Modularity Constraints (with N. Kakimura),
Advance in Applied Math 49 (2012), 97--110.
-
The Linear Distance Traveling Tournament Problem (with R. Hoshino), to appear in the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12).
-
Minors in 5-connected non-planar large graphs (with J. Maharry),
J. Graph Theory 78 (2012), 128--141.
-
Linkless and flat embeddings in 3-space (with S. Kreutzer and B. Mohar),
Discrete and Computational Geometry 47, (2012), 731--755.
-
Linear min-max relation between the treewidth of $H$-minor-free graphs and its largest grid minor (with Y. Kobayashi),
Symposium on Theoretical Aspects of Computer Science (STACS), 278--289, 2012.
-
Edge-disjoint Odd Cycles in $4$-edge-connected Graphs (with Y. Kobayashi), Symposium on Theoretical Aspects of Computer Science (STACS),
206--217, 2012.
-
A Linear Time Algorithm for the Induced Disjoint Paths Problem in
Planar Graphs (with Y. Kobayashi), Journal of Computer and System Sciences 78, (2012), 670--680.
-
The disjoint paths problem in quadratic time (with Y. Kobayashi and B. Reed),
J. Combin. Theory Ser. B 102 (2012), 424--435.
-
The Erdos-Posa property for clique minors in highly connected graphs (with R. Diestel and P. Wollan), J. Combin. Theory Ser. B, 102
(2012), 454--469.
-
Minimally contraction-critical 6-connected graphs (with K. Ando and S. Fujita),
Discrete Mathematics 302 (2012), 671--679.
-
Spanning closed walks and TSP in 3-connected planar graphs (with K. Ozeki),
to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12), 671--682.
-
Erd\H{o}s-P\'osa property and its algorithmic applications --- parity constraints, subset feedback set, and subset packing (with N. Kakimura and Y. Kobayashi), ACM-SIAM Symposium on Discrete Algorithms, (SODA'12), 1726--1826.
-
List-Coloring Graphs without Subdivisions and without Immersions (with Y. Kobayashi,
to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12), 1425--1435.
-
Improved Algorithm for the Half-Disjoint Paths Problem (with Y. Kobayashi), Siam J. Discrete Math, 25 (2011), 1322--1330.
-
The minimum $k$-way cut of bounded size is fixed-parameter tractable (with M. Thorup),
52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), 160--169.
-
The Graph Minor Algorithm with Parity Conditions (with B. Reed and P. Wollan),
52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), 27--36.
-
Scheduling Bipartite Tournaments to Minimize Total Travel Distance (with R. Hoshino),
Journal of Artificial Intelligence Research, 41 (2011), 527--561.
-
Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas),
ACM transaction on Algorithms 7 No. 41 (2011).
-
2- and 3-factors of graphs on surfaces (with K. Ozeki), J. Graph Theory, 67 (2011), 306--315.
-
A Multi-Round Generalization of the Traveling Tournament Problem and its Application to Japanese Baseball (with R. Hoshino),
European Journal of Operational Research, 215 (2011), 481--497.
-
The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports Schedule (with R. Hoshino),
the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11).
-
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs (with P. Klein and C. Sommer),
38th International Colloquium on Automata, Languages and Programming (ICALP 2011), 135--146.
-
Contraction Decomposition in $H$-Minor-Free Graphs and Algorithmic Applications (with E. Demaine and M. Hajiaghayi), the 43rd ACM Symposium on Theory of Computing (STOC'11), 441--450.
-
A simpler algorithm and shorter proof for the graph minor decomposition (with P. Wollan), the 43rd ACM Symposium on Theory of Computing (STOC'11), 451--458.
-
Finding topological subgraphs is fixed-parameter tractable (with M. Grohe, D. Marx and P.Wollan), the 43rd ACM Symposium on Theory of Computing (STOC'11), 479--488.
-
Breaking $O(n^{1/2})$-approximation algorithms for the edge-disjoint paths problem (with Y. Kobayashi), the 43rd ACM Symposium on Theory of Computing (STOC'11), 81--88.
-
The Distance-Optimal Inter-League Schedule for Japanese Pro Baseball (with R. Hoshino),
the ICAPS 2011 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS), 71--78.
-
The Multi-Round Balanced Traveling Tournament Problem (with R. Hoshino), the 21st International Conference on Automated Planning and Scheduling (ICAPS'11),
106--113.
-
Toughness of $K_{a,t}$-minor-free graphs (with G. Chen, Y. Egawa, B. Mohar, K. Ota), Electric J. Combinatorics.
-
Packing cycles through prescribed vertex set (with N. Kakimura and D. Marx),
J. Combin. Theory Ser. B 101, (2011), 54--59.
-
Matching extension versus representativity in 5-connected embedded graphs (with S. Negami, M. Plummer and Y. Suzuki), J. Combin. Theory Ser. B 101 (2011), 206--213.
-
Non-separating subgraphs after deleting many disjoint paths (with K. Ozeki),
J. Combin. Theory Ser. B 101, (2011), 54--59.
-
Contractible triples in highly connected graphs (with S. Fujita),
Annals of Combinatorics 14 (2010), 457--465.
-
Non-separating even cycles in highly connected graphs (with S. Fujita), Combinatorica 30, (2010), 565--580.
-
Algorithms for finding an induced cycle in planar graphs (with Y. Kobayashi),
Combinatorica, 30, (2010), 715--734.
-
A separator theorem in minor-closed classes (with B. Reed),
the 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), 153--162.
-
Immersing small complete graphs (with M. DeVos, B. Mohar and H. Okamura),
Ars Mathematica Contemporanea 3 (2010) 139--146.
-
A note on traversing specified vertices in graphs embedded with large representativity (with M. Plummer),
Discrete Math (Carsten Thomassen's 60), 310, 2655-2661 (2010).
-
Contractible small subgraphs in k-connected graphs (with S. Fujita),
Graphs and Combinatorics 26 (2010), 499--511.
-
An improved algorithm for the half disjoint paths problem (with Y. Kobayashi), Approx and Random 2010, 287-297.
-
An O(\log n) approximation algorithm for the edge-disjoint paths problem in eulerlian planar graphs and
4-edge-connected planar graphs (with Y. Kobayashi), Approx and Random 2010, 274-286.
-
Odd cycle packing (with B. Reed), 42nd ACM Symposium on Theory of Computing (STOC'10), 695--704.
-
A shorter proof of the Graph Minor Algorithm - The Unique Linkage Theorem - (with P. Wollan),
42nd ACM Symposium on Theory of Computing (STOC'10), 687--694.
-
Linkless and flat embeddings in 3-space and the Unknot problem (with S. Kreutzer and B. Mohar),
the 26th Annual ACM Symposium on Computational
Geometry, 97--106.
-
Double-critical graphs and complete minors (with A. S. Pedersen and B. Toft),
Electric J. Combinatorics, R87, (2010).
-
A simple algorithm for 4-coloring 3-colorable planar graphs (with K. Ozeki),
Theoretical Computer Science, 411 (2010), 2619--2622.
- Star-coloring and Acyclic-coloring of locally planar graphs (with B.
Mohar), Siam. J. Discrete Math. 24 (2010), 56--71.
- Recognizing a totally odd $K_4$-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements (with Z. Li and B. Reed), ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 318--328.
- Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs (with E. Demaine and M. Hajiaghayi),
ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 329--344.
-
The edge disjoint paths problem in Eulerian graphs and $4$-edge-connected graphs (with Y. Kobayashi),
ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 345--353.
-
An (almost) Linear Time Algorithm For Odd Cycles Transversal (with B. Reed), ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 365--378.
- Dominating sets in triangulations on surfaces (with T. Honjo and A. Nakamoto),
J. Graph Theory, 63 (2010), 17--30.
-
Planarity allowing few error vertices in linear time,
50th Annual Symposium on Foundations of Computer Science (FOCS 2009), 639--648.
- Hadwiger's Conjecture is decidable (with B. Reed),
the 41st ACM Symposium on Theory of Computing (STOC'09), 445--454.
- Highly parity linked graphs, (with B. Reed),
Combinatorica, 29 (2009), 215--225.
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs, (with E. Demaine and
M. Hajaghayi), 36th International Colloquium on Automata, Languages and Programming (ICALP'09), 316--327.
- Bounding the size of equimatchable graphs of fixed genus (with M. Plummer),
Graphs and Combinatorics 25 (2009), 91--99.
- Note on coloring graphs without odd Kk-minors, J. Combin. Theory Ser. B 99 (2009) 728--731.
- Decomposing planar graphs of girth five into an independent set and a forest (with C. Thomassen), J. Combin. Theory Ser B. 99 (2009), 674--684.
-
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction (with E. Demaine and M. Hajiaghayi), Algorithmica, 54 (2009), 142--180.
- List-coloring graphs without $K_{4,k}$-minors, Discrete
Applied Math, 157, (2009), 659--662.
- 6-critical graphs on the Klein bottle (with D. Kral, J. Kyncl, and B. Lidicky),
Siam J. Discrete Math, 23 (2009), 372--383.
-
Linear Connectivity forces large complete bipartite minors (with T. Bohme, J. Maharry
and B. Mohar), J. Combin. Theory Ser. B, 99 (2009), 557--582.
-
Removable paths in non-bipartite graphs (with O. Lee and B. Reed),
J. Combin. Theory Ser. B, 99 (2009), 30--38.
-
On the number of 4-contractible edges in 4-connected graphs (with K. Ando, Y. Egawa and
M. Krisell), J. Combin. Theory Ser. B, 99 (2009), 97--109.
-
$N$-flips in even triangulations on surfaces (with A. Nakamoto and Y. Suzuki),
J. Combin. Theory Ser. B, 99 (2009), 229--246.
-
Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
(with Y. Kobayashi), ACM-SIAM Symposium on Discrete Algorithms, (SODA'09), 1146--1155.
-
Additive approximation algorithms for list-coloring minor-closed class of graphs
(with E. Demaine and M. Hajiaghayi), ACM-SIAM Symposium on Discrete Algorithms, (SODA'09), 1166--1175.
-
Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas),
ACM-SIAM Symposium on Discrete Algorithms, (SODA'09), 1176--1182.
-
A nearly linear time algorithm for the half integral parity disjoint paths packing problem
(with B. Reed), ACM-SIAM Symposium on Discrete Algorithms , (SODA'09), 1183--1192.
-
List-Color-Critical Graphs on a Fixed Surface (with B. Mohar),
ACM-SIAM Symposium on Discrete Algorithms, (SODA'09), 1166--1175.
- Note on non-separating and removable cycles in highly connected graphs (with S. Fujita),
Discrete Applied Math, 159 (2009), 398--399.
- A simpler linear time algorithm for embedding graphs on a surface and for bounded
tree-width graphs (with B. Mohar and B. Reed),
49th Annual Symposium on Foundations of Computer Science (FOCS 2008) (2008), 771--780.
- A weaker version of the odd Hadwiger's conjecture, Combin. Prob. Computing,
17 (2008), 815--821.
- $K_6$-minor in triangulations in the Klein bottle (with R. Mukae and A. Nakamoto),
Siam. J. Discrete Math, 23, (2008), 96--108.
- Long cycles without hamiltonian paths (with K. Ozeki and T.
Yamashita), Discrete Math., 308, (2008), 5899--5906.
- Locally planar graphs
are 5-list-colorable (with M. DeVos and B. Mohar),
J. Combin. Theory Ser B. (2008), 98, 1215--1232
- A weaker version of Lovasz' path removable conjecture
(with O. Lee, B. Reed and P. Wollan), J. Combin. Theory Ser B.
(2008), 98, 972--979.
- Graph and Map isomorphism and all polyhedral embeddings in linear time (with B. Mohar),
40th ACM Symposium on Theory of Computing (STOC'08), 471--480.
- Improved upper bounds on the crossing number (with V. Dujmovic, B. Mohar and D. Wood),
Symposium on Computational Geometry 2008 (SOCG'08), 375--384.
- Connectivity keeping edges in graphs of large minimum degree (with
S. Fujita), J. Combin. Theory Ser. B, 98 (2008), 805--811.
- Approximating list-coloring on a fixed surface, 35th International Colloquium on Automata, Languages and Programming (ICALP'08) (2008), 333--344.
- Contractible subgraphs in $k$-connected graphas not containing
specified subgraphs (with S. Fujita),
J. Graph Theory 58 (2008), 97--109.
- The induced disjoint paths problem (with Y. Kobayashi), 13th Conf. on Integer Programming and Combinatorial Optimization - IPCO XIII 'IPCO'08), 47--61.
- An improved algorithm for cycles through elements, 13th Conf. on Integer Programming and Combinatorial Optimization - IPCO XIII (IPCO'08), 374--384.
- Fractional coloring and the odd Hadwiger's conjecture (with B.
Reed), Europ. J. Combinatorics 29 (2008), 411--417.
- A nearly linear time algorithm for half-integral disjoint paths
packing (with B. Reed), ACM-SIAM Symposium on Discrete Algorithms (SODA08) 446--454.
- Contractible edges in minimally k-connected graphs
(with K. Ando and A. Kaneko), Discrete Math, 308 (2008), 597--602.
- On the matching extention of graphs on a fixed surface
(with R. Aldred and M. Plummer), J. Combin. Theory Ser. B 98 (2008),
105--115.
- Non-separating cycles consisting of contractible edges in
$k$-connected graphs, (with Y. Egawa and K. Inoue),
Siam Discrete Math. 21 (2007), 1061--1070.
- Erdos-Chvatal condition and 2-factors (with G. Chen, R. Gould, K.
Ota, I. Schiermeyer, A. Saito), Discuss. Math. Graph
Theory 27 (2007) 401--408.
- Independent sets and complete minors (with Z. Song),
J. Graph Theory (2007), 219--226.
- Some Recent progress on Graph Minor Theory (with B. Mohar),
Graphs and Combinatorics, 23 (2007), 1--46..
- Computing crossing number in linear time (with B. Reed),
39th ACM Symposium on Theory of Computing (STOC'07), 382--390.
- Extremal Results For Rooted Minor Problems, (with L. Jorgensen)
Journal of Graph Theory 55 (2007) 191--207.
- A relaxed version of Hadwiger's conjecture for list-coloring
(with B. Mohar), J. Combin. Theory Ser. B 97 (2007), 647--651.
- Some remarks on the odd Hadwiger's conjecture (with Z. Song)
Combinatorica 27 (2007), 429--438.
- 2-connected spanning subgraph with low maximum degree on a fixed surface.
(with M. Ellingham), J. Combin. Thoery Ser. B 97 (2007) 401--412.
- The Erdos-Posa property for odd cycles in an orientable surface
(with A. Nakamoto), Discrete Math 307 (2007), 764--768.
- Half-integral packing, Erdos-Posa Property and Graph Minors,
ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 1187--1196
- Chords of longest circuits in locally planar graphs (with J. Niu and C.Q. Zhang),
Euro. J. Combinatorics 28 (2007), 315--321.
- On the connectivity of minimum and minimal-counterexamples to Hadwiger's conjecture,
J. Combin. Theory Ser. B. 97 (2007), 144--150.
- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction
(with E. Demaine and M. Hajiaghayi). ISAAC 2006: 3-15
-
Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs (with B. Mohar). STOC 2006: 401-416
- On sufficient degree conditions for a graph to be $k$-linked, (with A. Kostoshka and G. Yu),
Combinatorics, Probability and Computing. 15 (2006), 685--694.
- A pair of forbidden subgraphs and perfect matchings
(with S. Fujita, C.L. Lucchesi, K. Ota, M.D. Plummer and A. Saito),
J. Combinatorial Theory (B), 96 (2006) 315--324.
-
Non-zero disjoint cycles in highly connected group labelled graphs,
(with P. Wollan), J. Combin. Theory Ser. B. 96 (2006) 296--301.
-
Domination in a graph with a 2-factor (with M. Plummer and A. Saito).,
Journal of Graph Theory. 52 (2006) 1--6.
-
Nonseparating paths with two prescribed endvertices
in $4$-connected graphs, (with O. Lee and X. Yu), Annals
of Combinatorics 9 (2005) 47-56.
- On Structure of $k$-connected graphs without $K_k$-minor,
(with R. Luo, J. Niu and C.Q. Zhang), Europ. J. Combinatorics 26 (2005)
293-308.
- Graph Minors and Linkage Problems (with G. Chen, R. Gould, F. Pfender
and B. Wei), J. Graph Theory 49 (2005) 75-91.
- Some Properties of 5-contraction critical graphs, (with K. Ando and
A. Kaneko), Graphs and Combinatorics 21 (2005) 27-37.
- Acute triangles in 4-connected plane graphs, (with A. Nakamoto, Y. Oda and
M. Watanabe), Discrete Math. 292 (2005) 95-106
- Any $7$-chromatic graph has a $K_7$-minor or a $K_{4,4}$-minor
(with B. Toft), Combinatorica 25 (2005) 327-353.
- Improvements of the theorem of Duchet and Meynial's theorem on
Hadwiger's Conjecture, (with M. Plummer and B. Toft).
J. Combin. Theory Ser. B. 95 (2005) 152-167.
- Algorithmic graph minor theory: Decomposition, Approximation and
Coloring (with E. Demaine and M. Hajiaghayi), FOCS 2005.
- Existence of two long cycles (with Y. Egawa, S. Fujita and H. Wang).
Discrete Math 305 (2005) 154--169.
- Detecting Even Holes, (with M. Chudnovsky and P. Seymour),
J. Graph Theory, 48 (2005) 85-111.
- K-Linked Graphs with Girth Condition, J. Graph Theory 45 (2004) 48--50.
- Cycles through prescribed vertex set in n-connected graphs,
J. Combin. Theroy Ser. B. 90 (2004) 315--323.
- Vertex-Disjoint Cycles Containing Specified Vertices
in a Bipartite Graph
(with G. Chen, H. Enomoto, D. Lou, K. Ota and A. Saito),
Journal of Graph Theory 46 (2004) 145--166.
- Vertex-Disjoint K_l^-in a graph, Discuss Math Graph Theory.
24, (2004), 249--262.
- A theorem on paths in locally triangulations.,
Europ. J. Combinatorics 25 (2004) 781-784.
- Rooted minors problem in highly connected graphs,
Discrete Math. 287 (2004) 121-123.
- On properties of a set of global roundings associated with clique connection of graphs.
(with T. Ishikawa and T. Tokuyama),
Interdiscip. Inform. Sci. 10 (2004), 159--163
- Orientable and non-orientable genera for some complete tripartite graphs,
(with C. Stephen and X. Zha), Siam J. Discrete Math. 18 (2004) 479-487.
- Cycles Having the Same Modularity. (with K. Ando, M. Hagita, A. Kaneko,
M. Kano and A. Saito), Discrete Math. 265 (2003) 23--30.
- 7-coverings of 3-connected graphs on surfaces,
(with A. Nakamoto and K. Ota), Journal of Graph Theory. 43 (2003) 26--36.
- Some forbidden subgraph conditions for a graph to have a
$k$-contractible edge, (with K. Ando),
Discrete Math 267 (2003) 3--11.
- On two equimatchable graph classes,
(with M. Plummer and A. Saito), Discrete Math. 266 (2003) 263--274.
- Covering vertices of a graph by $k$ vertex disjoint cycles,
(with Y. Egawa, M. Hagita and H. Wang), Discrete Math. 270 (2003) 114--124.
- Subgraphs of Graphs on Surfaces with High Representativity,
(with A. Nakamoto and K. Ota), J. Combin. Theory Ser. B. 89 (2003), 207-229.
- Vertices of degree 6 in contraction critical graphs,
(with K. Ando and A. Kaneko), Discrete Math. 273 (2003) 55--69.
- One or two disjoint cycles cover independent edges: Lovasz-Woodall
Conjecture,
J. Combin. Theory Ser. B, 84 (2002) 1--44.
- Path Factor in Claw-Free Graphs,
(with K. Ando, Y. Egawa, A. Kaneko, H. Matsuda),
Discrete Math 243 (2002) 195--200.
- Graph partitions into paths containing specified vertices,
Discrete Math. 248 (2002) 271--278.
- $K_4^-$-factor in graphs ,
Journal of Graph Theory 39 (2002) 111--128.
- Hamiltonian Cycles in n-Extendable Graphs
(with K. Ota and A. Saito), Journal of Graph Theory. 40 (2002) 75--82.
- On a hamiltonian cycle in which specified vertices are not isolated,
(with A. Kaneko, K. Ota, and K. Yoshimoto),
Discrete Mathematics. 258 (2002) 85--91.
- Contractible edges and triangles in k-connected graphs,
Journal of Combinatorial Theory Ser. B. 85 (2002) 207--221.
- Path factor in cubic graphs, (with H. Matsuda, Y. Oda and
K. Ota), Journal of Graph Theory. 39 (2002) 188--193.
- $F$-factor and vertex disjoint $F$ in Graphs,
Ars Combinatoria 62 (2002) 183--187.
- Contractible edges and Bowtie in $k$-connected graphs,
(with K. Ando, A. Kaneko and K. Yoshimoto),
Ars Combinatoria 64 (2002) 237--248.
- Hamiltonian Cycles in Factor-Critical Graphs,
(with A. Saito and K. Ota),
Discrete Math 240 (2001) 71--82.
- Vertex-Disjoint Cycles Containing Specified Edges in a Bipartite Graph,
(with H. Enomoto, G. Chen, D. Lou, K. Ota and A. Saito.)
Australasian J. Combinatorics 23 (2001) 37--48.
- A Survey on Hamiltonian Cycles,
Interdisciplinary Information Science 7 (2001) 25--39.
- Contracting $4$-Connected Plane Triangulations into an Octahedron,
(with A. Nakamoto, Y. Oda and M. Watanabe),
Lecture Note on Computer Science 2098 (2001) 217--221.
- Note on contractible edges in $k$-connected graphs,
Australasian J. Combinatorics 24 (2001) 165--168.
- Contractible edges in $k$-connected graph containing no $K_4^-$,
(with K. Ando and A. Kaneko),
Sut J. mathematics, 36 (2000) 99--103.
- A Note on Hamiltonian Cycles in $(k,n)$-Factor-Critical Graphs,
Sut J. Mathematics, 36 (2000) 259--266.
- New approach to Lovász-Woodall conjecture. Paul Erd?s and
his mathematics (Budapest, 1999), 118--121, János Bolyai Math. Soc.,
Budapest, 1999.